...

суббота, 30 мая 2015 г.

VPN-расширение Hola продает пользовательский трафик и содержит уязвимости удаленного выполнения кода

4 дня назад, администратор борды 8chan (доска /beast/ которой заблокирована в России) сообщил о DDoS-атаке на сайт, которая выглядела как стократный приток обычных посетителей. Самое большое увеличение нагрузки получил скрипт для постинга post.php (капчи на борде не было); DDoS привел к падению PHP-FPM, под которым выполнялся скрипт. В ходе исследования трафика выяснилось, что для совершения атаки были использованы каналы пользователей с Hola — популярным браузерным расширенем для доступа к заблокированным сайтам, пользующееся популярностью как за рубежом, так и в России.
Пользователи расширения, сами того не зная, отдавали свои интернет-каналы дочерней фирме Luminati, которая, по сути, владела более 9 миллионами уникальных выходных нод, за счет расширения и каналов пользователей. Зарабатывают они, судя по всему, очень неплохо: первые 100 гигабайт трафика обходятся клиентам в $20 за гигабайт.

В FAQ проекта не было никаких упоминаний об использовании каналов пользователей, однако в Hola быстро добавили несколько пунктов на этот счет. Теперь, если вы не хотите отдавать свой канал Limunati, вам придется заплатить $5 в месяц.
Архивная версия FAQ
Текущая версия FAQ

После опубликования данной информации администратором 8chan, группа ребят нашла 4 уязвимости в данном расширении:

  • Чтение произвольных файлов до NULL-байта (/file_read.json)
  • Раскрытие уникального идентификатора пользователя (/callback.json)
  • Раскрытие адресов некоторых функций (/procinfo/ps, для последующего обхода ASLR)
  • Удаленное выполнение кода (/vlc_mv.json и /vlc_start.json)
  • Повышение привилегий до SYSTEM под Windows

Все версии Hola поднимают JSON REST HTTP-сервер на 127.0.0.1, но с заголовком Access-Control-Allow-Origin: *, что позволяет обращаться к нему с любой страницы в интернете. Windows-версии, которые устанавливают не только расширение в браузер, но и сервис, исполняются от имени SYSTEM.
Одну из уязвимостей удаленного выполнения кода, связанную с отсутствием фильтрации аргументов в строке запуска встроенного видеоплеера VLC, в Hola уже пропатчили, но исследовательская группа уверена, что ее просто спрятали подальше, чтобы эксплоит на сайте исследователей, запускающий калькулятор Windows, перестал работать.

На сайте «Adios, Hola!», посвященному уязвимостям в расширении, можно выполнить проверку, являетесь ли вы exit-нодой, можно ли вас идентифицировать, выполнить код от вашего и привилегированного пользователя SYSTEM. Также на сайте содержится подробная инструкцая по удалению всего комплекса для Chrome, Firefox, Internet Explorer и Android-версии.

На данный момент, расширение Hola удалено из Firefox Addons, но есть в Chrome Web Store, хоть и не находится в поиске. Призываю всех авторов списков ПО для обхода цензуры либо убрать Hola из списка вариантов, либо написать предупреждения о факте использования канала. Свой список, который, к слову, до сих пор пользуется большой популярностью, я обновил.

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

Информация от администратора 8chan
Техническая информация от исследователей
Самый крупный тред на Reddit
Новость на Vice
Новость на TJournal

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[recovery mode] «ВКонтакте» не платит пользователям за найденные уязвимости

29 мая ВКонтакте торжественно объявили о запуске открытой программы вознаграждений за уязвимости. Это, как и некоторые другие события, побудило меня на написание этой статьи. История началась еще в сентября 2014, когда во время написания мною сервиса, основанного на API социальной сети, я обнаружил уязвимость, которая позволяла узнавать как администратора сообщества, сделавшего пост, так и человека предложившего эту запись.

1. Обнаружение уязвимости


Уязвимость заключалась в методе API newsfeed.get. При выполнении самого обычного запроса к нему, в объекте, среди прочих, возвращался массив из 4-5 пользователей (profiles). Они, судя по документации, должны были являться пользователями из ленты новостей. Однако я никак не мог найти в ленте этих людей, и зачастую в массиве встречался только мой собственный аккаунт.

image

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

То есть, сделав к newsfeed.get запрос для получения последнего поста в ленте новостей, в массиве profiles мне возвращало администратора написавшего и пользователя предложившего как эту запись, так и предыдущие три.

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

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

image

Я написал скрипт, который первым делом создавал список новостей с определенным сообществом. Затем собирал для каждого поста этого сообщества свой массив с профилями. Здесь я столкнулся с лимитами API, оно отдавало мне посты лишь за последние 12 дней, но с этим тоже можно было работать.

После сбора массивов для максимально возможного количества постов, скрипт начинал их анализировать. Для начала находились те пользовательские id, которые встречаются ровно в четырех массивах. Из четырех постов, связанных с этими массивами я находил самый ранний. Этот пост был предложен в сообщество пользователем, чей id мы нашли. Затем эти пользователи отфильтровывались из массивов и мною составлялся список администраторов.
При желании вы можете посмотреть код эксплуатации уязвимости на Github

2. Сообщаем об уязвимости


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

Я знал об отсутствии официальной bug bounty программы у ВКонтакте, но также знал, что нередки были случаи поощрения за уязвимости внутренней валютой(голосами), однако решил отложить эти вопросы на момент исправления уязвимости. После этого я стал изредка мониторить уязвимость. Это продолжалось до апреля 2015, когда прочитав очередную статью об уязвимости и вознаграждении, я снова проверил свою уязвимость и она не была исправлена.

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

image

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

image

Со мной связались лишь 29 мая, спустя несколько часов после запуска программы вознаграждения за уязвимости, заявив, что раз “уязвимость уже исправлена, то она не подпадает под новую программу и им мне нечего предложить”.

Итоги


  1. Очередная уязвимость в приватности ВКонтакте
  2. Потребовалось 8 месяцев и 3 моих обращения для исправления
  3. Вопросы о вознаграждении игнорировались вплоть до запуска bug bounty программы, после чего мне под ее предлогом было отказано в какой-либо выплате
  4. Техподдержка предпочла длительное игнорирование каким-либо действиям

Автором поста является bleazer, у которого пока нет инвайта

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Data Lake – от теории к практике. Сказ про то, как мы строим ETL на Hadoop

В этой статье я хочу рассказать про следующий этап развития DWH в Тинькофф Банке и о переходе от парадигмы классического DWH к парадигме Data Lake.
Свой рассказ я хочу начать с такой вот веселой картинки :)

Да, ещё несколько лет назад можно картинка была актуальной. Но сейчас, с развитием технологий, входящих в эко-систему Hadoop и развитием ETL платформ правомерно утверждать то, что ETL на Hadoop не просто существует но и то, что ETL на Hadoop ждет большое будущее. Далее в статье расскажу про то, как мы строим ETL на Hadoop в Тинькофф Банке.

Перед управлением DWH была поставлена большая задача – анализировать интересы и поведение интернет посетителей сайта банка. У DWH образовалось два новых источника данных, больших данных – это clickstream с портала (www.tinkoff.ru) и RTB (Real-Time Bidding) платформа банка. Два источника порождают колоссальный объём текстовых полуструктурированных данных, что конечно для традиционного DWH, построенного в банке на массивно параллельной СУБД Greenplum, совсем не подходит. В банке был развернут кластер Hadoop, на основе дистрибутива Cloudera, он то и лег в основу целевого хранилища данных, а точнее озера данных, для внешних данных.

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


Рис.1 Концепция
  • RAW – слой сырых данных, сюда загружаем файлы, логи, архивы. Форматы могут быть абсолютно различные: tsv, csv, xml, syslog, json и т.д. и т.п.;
  • ODD — Operational Data Definition. Сюда мы загружаем данные в формате приближенном к реляционному. Данные здесь могут являться результатом предобработки данных из RAW перед загрузкой в DDS;
  • DDS — Detail Data Store. Здесь мы собираем консолидированную модель детальных данных. Для хранения данных в этом слое мы выбрали концепцию Data Vault;
  • MART – витрины данных. Здесь мы собираем прикладные витрины данных.

Почему Data Vault? У этого подхода есть и свои плюсы, и свои минусы.
Плюсы:

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

Минусы:
  • Основной минус для нас был обусловлен средой хранения (а точнее и обработки) данных и как следствие производительностью работы join операций. Как известно Hive не очень любит операции join, в силу того, что в итоге всё выливается в медленный map reduce.

Проанализировав тренды развития технологий Hadoop, мы решили использовать этот подход и засучив рукава принялись моделировать Data Vault для выше озвученной задачи.

Собственно, хочу рассказать несколько концептов, которые мы используем. Например, в загрузке визитов интернет-пользователей по страницам мы не сохраняем каждый раз URL визита. Все URL-ы мы выделили, в терминах Data Vault, в отдельный хаб (см. Рис. 2). Такой подход позволяет значительно сэкономить место в HDFS и более гибко работать с URL-ами на этапе загрузки и дальнейшей обработки данных.


Рис.2 Data Vault для визитов

Ещё один концепт относиться к области загрузки интернет пользователей. Мы не получаем на этапе загрузки в DDS единого интернет пользователя, а загружаем данные в разрезе систем источников. Таким образом загрузки в Data Vault из разных источников не зависят друг от друга.

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

  • Использование партиционирования в HDFS;
  • Эмуляция дистрибьюции по ключу в HDFS.

В результате каждый объект (таблица) Data Vault в своем DDL содержит:
PARTITIONED BY (ymd string, load_src string)

и
CLUSTERED BY (l_visit_rk) INTO 64 BUCKETS

Вот и подошли к самому интересному. Концепцию продумали, моделирование провели, создали структуры данных, теперь хорошо бы было бы это все наполнить данными.
Для того что бы обеспечить стабильный поток данных (файлов) в слой RAW мы используем Apache Flume. Для обеспечения отказоустойчивости и независимости от кластера Hadoop мы разместили Flume на отдельном сервере – получили такой как бы File Gate, перед кластером Hadoop. Ниже приведу пример настройки агента Flume для передачи портального syslog:

# *** Clickstream PROD syslog source ***

a3.sources  = r1 r2
a3.channels = c1
a3.sinks    = k1

a3.sources.r1.type = syslogtcp
a3.sources.r2.type = syslogudp
a3.sources.r1.port = 5141
a3.sources.r2.port = 5141
a3.sources.r1.host = 0.0.0.0
a3.sources.r2.host = 0.0.0.0
a3.sources.r1.channels = c1
a3.sources.r2.channels = c1
# channel
a3.channels.c1.type = memory
a3.channels.c1.capacity = 1000
# sink
a3.sinks.k1.type = hdfs
a3.sinks.k1.channel = c1
a3.sinks.k1.hdfs.path = /prod_raw/portal/clickstream/ymd=%Y-%m-%d
a3.sinks.k1.hdfs.useLocalTimeStamp = true
a3.sinks.k1.hdfs.filePrefix = clickstream
a3.sinks.k1.hdfs.rollCount = 100000
a3.sinks.k1.hdfs.rollSize = 0
a3.sinks.k1.hdfs.rollInterval = 600
a3.sinks.k1.hdfs.idleTimeout = 0
a3.sinks.k1.hdfs.fileType = CompressedStream
a3.sinks.k1.hdfs.codeC = bzip2

# *** END ***

Таким образом, мы получили стабильный поток данных в слой RAW. Дальше нужно разложить эти данные в модель, наполнить Data Vault, ну короче нужен ETL на Hadoop.

Барабанная дробь, гаснет свет, на сцену выходит Informatica Big Data Edition. Не буду в красках и много рассказывать про этот ETL инструмент, постараюсь коротко и по делу.

Лирическое отступление. Хочется сразу отметить, что Informatica Platform (в которую входит BDE), это не та всем знакомая Informatica PowerCenter. Это принципиально новая платформа интеграции данных от корпорации Informatica, на которую сейчас постепенно переносят весь тот большой набор полезных функций из старого и всеми любимого PowerCenter.

Теперь по делу. Informatica BDE позволяет достаточно быстро разрабатывать ETL процедуры (маппинги), среда очень удобная и не требует длительного обучения. Маппинг транслируется в HiveQL и выполняется на кластере Hadoop, Informatica обеспечивает удобный мониторинг, последовательность запуска ETL процессов, обработку ветвлений и исключительных ситуаций.
Например, вот так выглядит маппинг, который наполняет хаб интернет юзеров нашего портала (см. Рис. 3).


Рис.3 Маппинг

Оптимизатор Informatica BDE транслирует этот маппинг в HiveQL и сам определяет шаги исполнения (см. Рис. 4).


Рис.4 План выполнения

Informatica BDE позволяет гибко управлять параметрами среды выполнения. Например, мы у себя настроили следующие параметры:

mapreduce.input.fileinputformat.split.minsize = 256000000
mapred.java.child.opts = -Xmx1g
mapred.child.ulimit = 2
mapred.tasktracker.map.tasks.maximum = 100
mapred.tasktracker.reduce.tasks.maximum = 150
io.sort.mb = 100
hive.exec.dynamic.partition.mode = nonstrict
hive.optimize.ppd = true
hive.exec.max.dynamic.partitions = 100000
hive.exec.max.dynamic.partitions.pernode = 10000

Маппинги можно объединять в потоки. Например, у нас данные из отдельных систем источников загружаются в отдельных потоках (см. Рис. 5).


Рис.5 Поток загрузки данных

Informatica BDE обладает удобным инструментов администрирования и мониторинга (см. Рис. 6).


Рис.6 Мониторинг исполнения потока данных

Из преимуществ Informatica BDE можно выделить следующее:

  • Поддержка множества дистрибутивов Hadoop: Cloudera, Hortonworks, MapR, PivotalHD, IBM Biginsights;
  • Быстрая имплементация в продукт новых фич, разрабатываемых в Hadoop: поддержка новых версий дистрибутивов, поддержка новых версий Hive, поддержка новых типов данных в Hive, поддержка партиционированных таблиц в Hive, поддержка новых форматов хранения данных;
  • Быстрая разработка маппингов;
  • И ещё один очень важный аргумент в пользу Informatica — это очень тесное сотрудничество и партнерство с лидером рынка дистрибутивов Hadoop, компанией Cloudera. Этот аргумент позволяет определить стратегический выбор в пользу этих двух платформ, если в вы решили строить Data Lake.

Из недостатков можно выделить следующее:

  • Один большой, но не столь весомый, но все же недостаток – не хватает всего того множества полезных фич, которые есть в старом PowerCenter. Это гибкая работа с переменными и параметрами как внутри маппинга, так и на этапе взаимодействия workflow->mapping-> workflow. Но, новая платформа Informatica развивается и с каждой новой версией становиться более удобной.

В целом инструмент Informatica BDE весьма хорошо показал себя при работе с Hadoop и у нас на него дальше очень большие планы в части ETL на Hadoop. Думаю, в скором времени напишем ещё более предметные статьи о реализации ETL на Hadoop на Informatica BDE.


Основной результат, который мы получили на данным этапе — это стабильно работающий ETL, наполняющий DDS. Результат был получен за два месяца, командой из двух ETL разработчиков и архитектора. Сейчас мы ежедневно прогоняем через ETL на Hadoop ~100Gb текстовых логов и получаем в Data Vault примерно на порядок меньше данных, на основе которых собираются витрины данных. Загрузка в модель происходит на ночном регламенте, загружается дневной инкремент данных. Длительность загрузки составляет ~2 часа. С этими данными, выполняя Ad-hoc запросы, работают аналитики через Hue и IPython.
  • Переход на CDH 5.4 (сейчас работаем на 5.2) и пилотирование Hive 0.14 и технологию Hive on Spark;
  • Обновление Informatica 9.6.1 Hotfix2 до Hotfix3. И конечно ждем Informatica 10;
  • Разработка маппингов, собирающих витрины для работы машинного обучения и data scientist-ов;
  • Развитие ILM в Hadoop/HDFS.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Устройство уровней в NES-играх

В этой статье я попробую рассказать о способе хранения уровней в ROM-памяти картриджей для приставки NES.
Я опишу все основные способы и подробно остановлюсь на наиболее часто используемом (из нескольких десятков исследованных мной игр он встречался практически в каждой).

Данный способ я назвал «блочным» (оговорюсь, что многие термины в статье были придуманы мной, так как материалов на данную тему на русском нет; после исследования нескольких игр я занялся изучением англоязычных материалов и документации к редакторам игр для старых платформ, тогда уже нашлись некоторые аналогии, в таких случаях буду приводить свои термины с объяснением их значения и их английские версии). В качестве примеров я буду приводить уровни из игры «Darkwing Duck», а также других игр компании «Capcom», разобранных мной несколько лет назад.

Я постараюсь пропустить описание использования дизассемблера и техническую часть исследования (если будет интерес, можно сделать на эту тему отдельную статью), а остановлюсь на описании, как именно разработчики хранили данные. Зная, что именно искать, найти это внутри образа ROM станет намного проще. Бонусом я покажу готовый редактор уровней и несколько созданных на нём хаков классических NES-игр.


Итак, начнём описание, как положено исследователям кода, снизу вверх.

Нижний уровень будет самым сложным, но разбираться с ним полностью совсем необязательно, достаточно иметь приблизительное представление. Более того, можно пропустить эту часть вообще и продолжить чтение со следующего абзаца.
Я лишь опишу в нескольких предложениях происходящее тут и перейду к более интересным вещам.
Видеопроцессор NES имеет несколько экранных страниц — одна из них отображается на экране. В экранной странице хранятся номера тайлов размером 8x8, которые нужно отобразить (30 рядов по 32 тайла, всего 960 байт) и их атрибуты (дополнительные биты цвета тайлов), на всю страницу уходит 1 килобайт описания, так компактно описывается целый экран. Сами тайлы берутся из знакогенератора (на 256 тайлов размером 8x8 расходуется 4 килобайта памяти, по 16 байт на один тайл), они могут быть расположены как в отдельном видеобанке картриджа, так из копироваться в видеопамять из обычного банка с данными. Для исследователя место их хранения практически не важно. Желающим более подробно разобраться с этой темой могу посоветовать почитать статью от MiGeRa на русском языке

Просмотреть содержимое знакогенераторов видеопроцессора можно с помощью любого эмулятора NES, я буду использовать наиболее продвинутый для исследования игр — FCEUX (на момент написания статьи последняя версия 2.2.2), в нём для этого нужно выбрать пункт меню Debug->PPU Viewer:

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

Как уже упоминалось выше, на описание одного экрана с помощью тайлов уходит 960 байт (30x32 тайлов). Но посмотрите на полную карту первого уровня «Darkwing Duck».
Она состоит из 20 экранов. Если хранить описание всех экранов потайлово, то на сохранение одного уровня уйдёт примерно 18 килобайт, а на всех семи игровых уровней — 131 килобайт. Напоминаю, что это не сама видеопамять в образе игры, а только описание с помощью тайлов видеопамяти игровых экранов! Это больше всего суммарного размера банков данных во всём образе ROM «Чёрного Плаща» (там всего 128 кб суммарно на код и данные и ещё 128 кб на видеобанки). Более того, уровни «Duck Tales 2» содержат до 32 экранов, при том, что образ весит вдвое меньше.
Тут стоит задать себе вопрос, как можно хранить описание экранов экономнее? Что бы вы сделали на месте разработчиков?

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

Сжатие.
Почти не применяется в NES-играх (зато постоянно применяется в играх на Sega Mega Drive и Snes) в основном по причине малого количества доступной оперативной памяти, которая требуется для хранения распакованных данных, а также медленного процессора. Тем не менее, изредка встречается RLE-сжатие
Пример — первая «Contra» (совместно с описанием экранов с помощью блоков, см. дальше 3-й способ про блоки):

Выделенные красным блоки сохранены в образе ROM в виде «7 раз повторить блок с платформой», а синим, соответственно, «3 раза повторить блок с платформой». Можно убедиться в этом, скачав редактор для этой игры.
Стоит заметить, что RLE на NES всё же используют, но не для сжатия описания уровня, а для более подходящих для этого сущностей. Например, сжимают им тайлы, хранящиеся в этом случае в банках данных («Duck Tales 2», та же «Contra»). Распаковка при этом происходит сразу в видеопамять. Также иногда сжимают текстовые данные (подходящими для этого алгоритмами), но для описания уровня на данной платформе это всё же экзотика.

Рисование на чистом холсте.
Данный подход подразумевает то, что большая часть экрана остаётся чистой, поэтому описывать её не надо. Описывается только по каким координатам должны быть нарисованы конкретные объекты. Яркий пример такого подхода — игры серии «Марио»:


При таком подходе в памяти хранятся записи, которые расшифровываются в виде «нарисовать по координатам X,Y объект ЯЩИК». (Вместо «ЯЩИК» может быть любой игровой объект). Всё остальное пространство остаётся залито фоновым цветом и тратить драгоценные байты на его описание не нужно. Получается, что на одну такую запись расходуется всего 3 байта, а на одном экране будет нарисовано всего 5-6 объектов. Конечно, нужно потратить ещё несколько десятков байт на описание самих объектов, но это не идёт ни в какое сравнение с тем, чтобы хранить почти килобайт данных при описании всего экрана тайлами. А если вы присмотритесь к скриншотам повнимательнее, то узнаете страшную тайну «Super Mario Bros.» Облако и куст — это один и тот же объект, но нарисованный с разной палитрой. На что только не пойдут разработчики ради экономии нескольких байт. Кроме того, если исследовать способ записи информации об объектах на экране, то можно узнать, что и здесь использует вариация сжатия RLE, в записи можно указать, что несколько ящиков (как и любых других объектов, например, черепах) должно быть отображено подряд с помощью одного дополнительного байта. Кстати, о таком способе записи можно догадаться по дизайну уровней или врагов игры — если часто встречаются несколько одинаковых подряд идущих объектов, вероятно, может встретиться такой способ хранения информации о них.

Блочный
Основной и самый часто встречаемый способ экономии места для сохранения данных об игровых уровнях — блочный, при котором уровень описывается не тайлами 8x8, а большими единицами данных. Сами единицы данных (блоки) могут быть разного размера — самый часто встречаемый для NES размер в 2x2 тайла, т.е. размер блока 16x16 пикселей (в играх на Sega Mega Drive часто встречаются и блоки размером 4x4 тайлов). При этом сами блоки могут быть организованы в большие структуры — макроблоки (2x2 блока, 32x32 пикселей в большинстве случаев).

В левой части картинки показано объединение четырёх тайлов в один блок, в правой части — объединение четырёх блоков в один макроблок луны из первого уровня «Darkwing Duck».
Из скриншота должен быть понятен основной принцип объединения.

Примечание: ромхакеры часто называют блоки «Tiles», а макроблоки — «Tile Sprite Assembly (TSA)», что создаёт путаницу в понятиях тайла как символа/иконки в знакогенераторе и тайла как объединения нескольких других тайлов в одну структуру (TSA первого уровня и второго). Поэтому я позволю себе сохранить введённые мной названия.

В разных играх могут быть разные, но похожие системы блоков и макроблоков. В «Batman» размер макроблока — 2x1, за счёт чего фон выглядит менее блочным, во «Flintstones: Rescue Dino and Hoppy» макроблоки огромны (по 16 блоков), а в «New Ghostbusters 2» нету макроблоков, а комнаты составлены из обычных блоков. Принцип не меняется — уровень сохраняется как массив из чисел, кодирующий номера больших по размеру структур, составленных из более маленьких.
Например, описание первого экрана первого уровня в «Darkwing Duck» начинается в образе ROM по адресу 0x10 (это самое начало образа после 16 байт заголовка). Первые 8 байт — это первая строка экрана, 8 номеров макроблоков, которые будут отображены первыми, можете попробовать изменить их вручную, запустить игру, начать первый уровень и посмотреть результат. Следом описывается вторая строка, третья и так далее, один экран занимает 8 строк, дальше следует описание второго экрана. Описание экранов может идти не в том порядке, в котором они будут встречаться в игре. В каком-то смысле сами игровые экраны тоже можно представить огромными структурами из 8x8 макроблоков, из которых лепится сам уровень (весь уровень в этом случае называется «раскладкой»(англ. layout) игровых экранов). Экран не обязательно может иметь размер 8x8, зачастую встречаются экраны размером 8x6, верхняя и нижняя строка используются игрой для отрисовки интерфейса. Часто можно увидеть на экране тайлы, которые ни при каких обстоятельствах не могут быть отображены игрой из-за особенностей движка (либо из-за ограничений скроллинга, либо из-за особенностей программирования, например, в «Tiny Toon Adventures» на уровнях ввысоту «съедается» половина макроблока на стыке двух экранов). В некоторых играх нету разделения на экраны, и весь уровень описывается одной большой матрицей индексов макроблоков.

Как узнать из каких структур (макроблоков) состоит уровень конкретной игры?
Для этого нужно найти описание уровня внутри образа ROM с помощью дизассемблера или другим способом и изменить один или несколько байт в этом описании, чтобы посмотреть, что произойдёт на экране:



На картинках — примеры разных размеров макроблоков в разных играх (2x2 тайла в «Chip & Dale 2», 4x4 тайла в «Jungle Book», 4x8 тайлов в «Flintstones Surprise of Dinosaur Peak»).

Ещё раз — всё в уровнях игр на NES описывается блоками (ну, и макроблоками). При этом описание макроблоков чаще всего состоит просто из индексов отдельных блоков (при размере макроблока 2x2 — 4 индекса блока, всего 4 байта, для «Чёрного Плаща» слева-направо и сверху-вниз), а вот описания блоков включают в себя дополнительную информацию — цвет всего блока и его характеристику, является ли блок фоном, платформой, на которой можно стоять, подбираемым предметов или шипами, которые наносят урон и т.п. Разумеется, встречаются игры, в которых данное правило не соблюдается (например, в «Ninja Cats» цвет задаётся сразу для всего макроблока, а в «Chip & Dale 2» информация о типе блока закодирована просто в самом его номере). Другое отличие — порядок хранения частей макроблоков в памяти, они могут идти последовательно (4 байта на описание первого макроблока, затем 4 байта на описание следующего и т.д. зачастую по 256 штук на уровень), либо же хранится отдельно (например, в «Tiny Toon Adventures» сначала хранятся все левые верхние кусочки макроблоков, за ним все левые правые кусочки, потом нижние левые и правые четвертинки соотвественно).

Однако общие принципы блочного построения соблюдаются везде, что позволяет, во-первых, быстро находить похожие структуры в разных играх, во-вторых, изучать, в каких играх использовались похожие движки. Так, например, уровни «Darkwing Duck» с точностью до указателей на наборы блоков и макроблоков соотвествуют таковым в игре «Tale Spin» (хотя сам движок взят из «MegaMan 4», в котором наборы блоков и макроблоков были разделены по разным банкам, но с сохранением одинаковых указателей на них), и очень похожи на уровни «Chip & Dale» (отличия только в способах хранения вспомогательной информации уровня — в том, как записывается способ скроллинга экранов и кодов дверей между комнатами). Вторые же «Chip & Dale» сделаны совсем по другому, экраны в них описываются не макроблоками, а обычными блоками размером 2x2, и поэтому описание занимается намного больше места, так что сами экраны на уровнях регулярно повторяются, хотя благодаря дизайнерской работе неподготовленный игрок этого не замечает (в первой зоне первого уровня, например, циклически повторяются всего 3 экрана).

Исследуя игры, я писал для proof-of-concept программу CadEditor, которая отображала бы уровни из образов ROM так, как они выглядят в ходе прохождения игры на консоле.

Со временем она обрастала функционалом редактора, и ромхакеры даже сделали с её помощью несколько замечательных хаков (в основном на «Capcom»-классику), а также с десяток демок.
Вот одно из прохождений хака «Darkwing Duck In Edoropolis»:

Текущая версия редактора позволяет изменять уровни для 50 игр на платформы NES и Sega Mega Drive (для многих игр только по одному уровню, и часто требуется «доработка напильником», так что потребуются знания в ромхакинге).
Как упоминалось выше, код писался для себя, поэтому не отличается хорошим качеством, многие вещи сделаны топорно. Редактором я почти не занимаюсь из-за нехватки времени, но с радостью объяснил бы код кому-либо, кто захотел бы дорабатывать его или писать конфиги для подключения новых игр.

Надеюсь, данная статья позволит желающим немного разобраться в том, как были устроены уровни в старых играх (кстати, не только для NES, но и для остальных приставок с тайловой графикой — Sega Mega Drive, SNES, GBA и другие). Если у читателей возникнет интерес, могу написать ещё несколько статей похожей тематики, например: технический процесс поиска данных об уровнях (с помощью дизассемблера либо скриптов коррапта файлов), отличия в устройстве уровней для сеговских игр, устройство систем анимаций персонажей, поиск объектов на уровнях или создание вспомогательных инструментов для исследования.

Ссылки:
Исходники редактора
Тема на форуме с обсуждением редактора

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

DevConf 2015: Интервью с автором — PHP6 не будет! Встречаем PHP7


На вопросы оргкомитета DevConf 2015 отвечает Дмитрий Стогов - лидер проекта PHPNG и один из основных разработчиков PHP; ведущий инженер в Zend Technologies.

— Расскажите пару слов о себе.

Последние лет 10 работаю в Zend, где 2/3 времени занимаюсь развитием Open Source PHP, и, в основном, усовершенствованиями связанными с производительностью. Собственно, почти все что связано с производительностью в PHP-7 (да и в PHP-5) придумано или заимствовано и реализовано мной.

— Можете сказать пару слов о своём докладе помимо того, что есть в описании?

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

— На кого ориентирован Ваш доклад?

На всех разработчиков и администраторов, планирующих использовать PHP-7

— Что нового узнает слушатель Вашего доклада?

Я попытаюсь собрать все вместе и представить информацию в соответствии с текущим статусом PHP-7. Многое, что было предложено в RFC, для PHP-7 было переделано позже.

До встречи на конференции DevConf 2015 19 июня!

Видео с доклада прошедшей Devconf 2014: phpng — новый движок для старого php

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

DNS и refresh

Устроился как-то Иван Сергеевич на новую работу сисадмином.
Работа — шик, всё предыдущим админом настроено и задокументировано. Но вот беда, начальство сказало — надо новый домен в зоне ру теперь получить и всю почту перенастроить на него.

— Ну, не проблема, почту переносить мы умеем, а домен — тем более легко, — сказал Иван Сергеевич и пошел покупать домен.
Купил, сидит ждет, когда же домен начнет работать, nslookup значит мучает…

А результата-то и нету, он уже и яндекс и гугл пытал, но все получает: не удалось найти домен: Non-existent domain…
Что ж за напасть-то такая…
И начал Иван Сергеевич думать, да исследовать ситуацию эту, помня о том, что бесплатный домен на старой работе в неизвестной всем зоне начал резолвиться через минут пятнадцать.

И в RFC1537 он увидел такое:

— Refresh: The SOA record of the primary server is checked
every «refresh» time by the secondary servers;
if it has changed, a zone transfer is done.


И решил он посмотреть на зону ru: refresh = 86400 (1 day).
То есть обновится она в течение суток, может через час, а может и через 24 часа… Тут как повезет.
Тут уже стало ему интерсно, а в других странах — зонах так же ли?

И выяснилось:
.com — 30 минут
Индия (.in) — 10 минут
Мексика (.mx) — 15 минут
Китай (.cn) — 2 часа
США (.us) — 15 минут
Англия (.uk) — 2 часа
Казахстан (.kz) — 4 часа
Северная Корея (.kp) — 8 часов
Южная Корея (.kr) — 1 час
Украина (.ua) — 2 часа

Что ж такое, подумал Иван Сергеевич, почему у нас обновление зоны значительно дольше всех?
Сие осталось для него загадкой…
Однако на следующий день, уже ближе к вечеру, он отчитался перед начальством о том, что всё работает и настроено, но обида на неработающий вовремя DNS осталась с ним навсегда.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Sexy primes, «медленный питон» или как я бился о стену непонимания

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

Вот и мне в очередной раз «спустили» такую идею в немаленьком-таком legacy проекте. Не совсем переписать, не совсем все (ну в перспективе). В общем перейти с питона (а у нас там еще и тикль модульно присутствует) на scala. Речь пока шла о разработке новых модулей и сервисов, т.е. начинать с наименее привязанных к middle-level и front-nearby API's. Как я понял в перспективе возможно совсем.

Человек — не разработчик, типа нач-проекта и немного продажник (для конкретного клиента) в одном лице.

Я не то, что бы против. И скалу уважаю и по своему люблю. Обычно я вообще открыт ко всему новому. Так например, местами кроме тикля и питона у нас появляются сервисы или модули на других языках. Так например, мы переехали с cvs на svn, а затем на git (а раньше, давно-давно, вообще MS-VSS был). Примеров на самом деле масса, объединяет их один момент — так решили или как минимум одобрили сами разработчики (коллективно ли, или была группа инициаторов — не суть важно). Да и дело в общем в аргументах за и против.

Проблема в том, что иногда для аргументированной дискуссии «Developer vs. Anybody-Else» у последнего не дотягивает уровень знаний «материи» или просто невероятно сложно донести мысль — т.е. как-бы разговор на разных языках. И хорошо если это кто-нибудь типа software architect. Хуже если имеем «беседу» например с чистым «продажником», огласившим например внезапные «требования» заказчика.

Ну почему никто не предписывает, например, плиточнику — каким шпателем ему работать (типа с зубцами 10мм клея же больше уйдет, давайте может все же 5мм. А то что там полы-стены кривущие никого не волнует). И шуруп теоретически тоже можно «закручивать» молотком, но для этого же есть отвертка, а позже был придуман шуруповёрт. Утрирую конечно, но иногда действительно напоминает такой вот абсурд.
Это я к тому, что инструмент в идеале должен выбирать сам разработчик или иметь в этом как минимум последнее слово — ему с этим инструментом работать или мучиться.

Но что-то я отвлекся. В моей конкретной истории аргументов — за scala, у человека как всегда почти никаких.
Хотя я мог бы долго говорить про вещи, типа наличие разрабов, готовые наработки, отточенную и отлаженную систему и т.д. и т.п. Но зацепился за его «Питон очень медленный». В качестве примера он в меня кинул ссылкой на Interpreting a benchmark in C, Clojure, Python, Ruby, Scala and others — Stack Overflow, которую он даже до конца не прочитал (ибо там почти прямым текстом есть — не так плохо все с питоном).

Имелось ввиду именно вот это (время указано в секундах):

  Sexy primes up to:        10k      20k      30k      100k
  ---------------------------------------------------------
  Python2.7                1.49     5.20    11.00       119     
  Scala2.9.2               0.93     1.41     2.73     20.84
  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01


Разговаривать с ним на уровне, про чисто техническую сторону, нет ни малейшего желания. Т.е. про выделение памяти/пул объектов, GC (у нас не чистый CPython, скорее похож на RPython или pypy с собственным Jit, MemMgr, GC), про всякий сахар, с которым человек, писавший бенчь, немного переборщил и т.д.
Мой ответ был «любят разрабатывать на питоне не за это» и «на нем так не пишут, по крайней мере критичный к скорости код». Я немного слукавил и естественно понимаю, что этот пример для benchmark искусственный, ну т.е. значит чисто померить скорость. Но и болячки, которые при таком тесте повыскакивают в CPython, мне тоже известны.
Поэтому все же постарался на этом конкретном примере показать почему этот тест не целесообразен, ну или почему не совсем объективный что ли.

Начал с того, что показал ему этот тест и результаты исполнения (помечены звездой) в PyMNg (что есть наша сборка), pypy2, pypy3 и python3 (который то же был по тем же понятным причинам медленный). Железо конечно другое, но порядок думаю примерно одинаков.

  Sexy primes up to:        10k      20k      30k      100k
  ---------------------------------------------------------
  PyMNg                *   0.10        -        -      2.46
  pypy2                *   0.13        -        -      5.44
  pypy3                *   0.12        -        -      5.69
  ---------------------------------------------------------
  Python3.4            *   1.41        -        -    117.69
  ---------------------------------------------------------
  Python2.7                1.49     5.20    11.00    119.00
  Scala2.9.2               0.93     1.41     2.73     20.84
  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01


Дальше можно было в принципе не продолжать, просто хотелось сделать попытку объяснить человеку, в чем он не прав, что выбор языка не оценивается по бенчмаркам типа «Hello, world» и т.д.

Итак, задача — ищем «сексуальные» пары простых чисел на питоне. Много и быстро.

Для тех кому разбор полетов не интересен, ссылка на скрипт на github, если есть желание поиграться.

Результаты исполнения каждого варианта под спойлером соответственно.
100K для всех вариантов.

pypy3 sexy-primes-test.py 100K
  org =  5.69000 s =   5690.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod1 =  2.45500 s =   2455.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod2 =  1.24300 s =   1243.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 org2 =  3.46800 s =   3468.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

  max =  0.03200 s =     32.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 orgm =  0.13000 s =    130.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev1 =  0.01200 s =     12.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev2 =  0.01000 s =     10.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie1 =  0.01200 s =     12.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie2 =  0.00200 s =      2.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]


python34 sexy-primes-test.py 100K
  org = 120.75802 s = 120758.02 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod1 = 132.99282 s = 132992.82 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod2 = 76.65101 s =  76651.01 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 org2 = 53.42527 s =  53425.27 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

  max =  0.44004 s =    440.04 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 orgm =  0.39003 s =    390.03 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev1 =  0.04000 s =     40.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev2 =  0.04250 s =     42.50 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie1 =  0.04500 s =     45.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie2 =  0.04250 s =     42.50 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]


10M начиная с варианта max (остальные просто медленные на таком массиве).
pypy3 sexy-primes-test.py 10M max
  max =  5.28500 s =   5285.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

 orgm = 12.65600 s =  12656.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev1 =  0.51800 s =    518.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev2 =  0.23200 s =    232.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie1 =  0.26800 s =    268.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie2 =  0.22700 s =    227.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]


python34 sexy-primes-test.py 10M max
  max = 288.81855 s = 288818.55 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

 orgm = 691.96458 s = 691964.58 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev1 =  4.02766 s =    4027.66 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev2 =  4.05016 s =    4050.16 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie1 =  4.69519 s =    4695.19 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie2 =  4.43018 s =    4430.18 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]


100M начиная с варианта siev1 (по той же причине).
pypy3 sexy-primes-test.py 100M siev1
siev1 =  7.39800 s =   7398.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

siev2 =  2.24500 s =   2245.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie1 =  2.53500 s =   2535.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie2 =  2.31000 s =   2310.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]


python34 sexy-primes-test.py 100M siev1
siev1 = 41.87118 s =  41871.18 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

siev2 = 40.71163 s =  40711.63 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie1 = 48.08692 s =  48086.92 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie2 = 44.05426 s =  44054.26 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]


Кстати такой разброс между CPython и PyPy и является часто одной из причин, почему люди переходят на PyPy, пишут собственные алокаторы, менеджеры памяти, GC, stackless и иже с ними, используют сторонние модули (например NumPy) и делают собственные сборки. Например, когда важна скорость исполнения и как здесь, имеем «агрессивное» использование пула объектов / множественные вызовы и т.д. Так же было когда-то давно и в нашем случае, когда мы переехали с чистого питона. Там еще было много чего и тормозящий multithreding и refcounting и т.д. Но сам переезд был обдуманным решением всей команды, а не «спущенной» сверху причудой. Если есть интерес и найду время, можно будет попробовать тиснуть про это статью.

Для этой же конкретной «задачи», можно было бы написать собственный C-binding, использовать модули типа numpy и т.д. Я же попробовал убедить коллегу, что оно, на коленке, за незначительное время решается практически «алгоритмически», если знаешь как питон тикает внутри.

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

Оригинальный скрипт, немного измененный мной для читабельности и поддержки третьего питона, этот вариант у меня в скрипте-примере называется org. (Только плз, не надо здесь про «xrange vs range» — я прекрасно представляю в чем различие, и здесь конкретно оно не суть важно, тем более в 3-м питоне, кроме того и итерация как-бы «завершенная»).

def is_prime(n):
  return all((n % i > 0) for i in range(2, n))
# def sexy_primes_below(n):
#   return [[j-6, j] for j in range(9, n+1) if is_prime(j) and is_prime(j-6)]
def sexy_primes_below(n):
  l = []
  for j in range(9, n+1):
    if is_prime(j-6) and is_prime(j):
      l.append([j-6, j])
  return l


Т.к. даже на 10M имеем всего 100K sexy пар, изменение оригинальной primes_below на мой вариант с прямым циклом не сильно влияет на время исполнения, просто оно наглядней для изменений в последующих вариантах (например сито). Весь цимес в реализации is_prime, во всяком случае пока.

1. Во первых, использование такого «сахара» как в оригинале (тем более в «сборках» типа PyPy, ну или нашего PyMNg) не поощряется, ну или как минимум, как и в этом случае, больно бьет отдачей в виде снижения скорости. Перепишем это как вариант mod1

def is_prime(n):
  i = 2
  while True:
    if not n % i:
       return False
    i += 1
    if i >= n:
       return True
  return True


Уже быстрее, как минимум в PyPy. Но дело не в этом…

2. Код стал сразу наглядней и видно, что его можно переписать как mod2 в половину быстрее, если не проверять четные номера (которые, кроме двойки, изначально не prime).

def is_prime(n):
  if not n % 2:
    return False
  i = 3
  while True:
    if n % i == 0:
       return False
    i += 2
    if i >= n:
       return True
  return True


Поправим это в оригинале — org2 это то же самое что и mod2, но в одну строчку используя «сахар».
def is_prime(n):
  return n % 2 and all(n % i for i in range(3, n, 2))


3. Если проверять делители до значения квадратного корня (правильно было бы до округленного, но мы сделаем проще — это же просто тест), то все можно сделать еще на много быстрее, получим вариант max:
def is_prime(n):
  if not n & 1:
    return 0
  i = 3
  while 1:
    if not n % i:
       return 0
    if i * i > n:
       return 1
    i += 2
  return 1

Намного быстрее, правда.

Опять правим это в оригинале — orgm.

def is_prime(n):
  #return ((n & 1) and all(n % i for i in range(3, int(math.sqrt(n))+1, 2)))
  return ((n & 1) and all(n % i for i in range(3, int(n**0.5)+1, 2)))


И видим, что как минимум в PyPy оно опять выполняется медленнее (хотя частично возможно и из-за прямого подсчета «корня», который в range).

4. Тут у коллеги загораются глаза, и он как в том мультфильме (по моему «Жадный богач») про скорняка и 7 шапок выдает: «А можешь еще быстрее?». Т.к. по памяти ограничения нет (не emdedded и т.д.) решил ему быстро переделать, используя «половинчатое» сито — half sieve, что есть подготовленный массив флажков по смещению для нечетных чисел, т.е. разделенных на 2. Тем более, что на питоне организовать такое сито на раз-два.
Ну и сразу видоизменяем sexy_primes_below, вызвав в нем генерацию сита ну и чтобы не править is_prime и не вызывать его в цикле, спрашиваем сразу sieve.
Получаем вариант siev1.

def primes_sieve(n):
  """ temporary "half" mask sieve for primes < n (using bool) """
  sieve = [True] * (n//2)
  for i in range(3, int(n**0.5)+1, 2):
    if sieve[i//2]:
      sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
  return sieve
def sexy_primes_below(n):
  l = []
  sieve = primes_sieve(n+1)
  #is_prime = lambda j: (j & 1) and sieve[int(j/2)]
  for j in range(9, n+1):
    i = j-6
    #if (i & 1) and is_prime(i) and is_prime(j):
    if (i & 1) and sieve[int(i/2)] and sieve[int(j/2)]:
      l.append([i, j])
  return l

Этот вариант настолько быстрый, что в PyPy например он на 100M выдает практически то-же время, что оригинал на 100K. Т.е. проверяя в 2000 раз больше чисел и генерируя на несколько порядков больший список сексуально-простых пар.

Сразу переписал в вариант siev2, потому что вспомнил о несколько «туповатой» обработке bool в PyPy. Т.е. заменив булевы флажки на 0/1. Этот пример отрабатывает на 100M уже вдвое-трое быстрее оригинала на 100K!

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

sieve = [1, 1, 1, 0, 1, 1 ...]; # для 3, 5, 7, 9, 11, 13 ...
osieve = [3, 5, 7, 0, 11, 13, ...]; # для 3, 5, 7, 9, 11, 13 ...


Вариант osiev1.
def primes_sieve(n):
  """ temporary odd direct sieve for primes < n """
  sieve = list(range(3, n, 2))
  l = len(sieve)
  for i in sieve:
    if i:
      f = (i*i-3) // 2
      if f >= l:
        break
      sieve[f::i] = [0] * -((f-l) // i)
  return sieve
def sexy_primes_below(n):
  l = []
  sieve = primes_sieve(n+1)
  #is_prime = lambda j: (j & 1) and sieve[int((j-2)/2)]
  for j in range(9, n+1):
    i = j-6
    #if (i & 1) and is_prime(i) and is_prime(j):
    if (i & 1) and sieve[int((i-2)/2)] and sieve[int((j-2)/2)]:
      l.append([i, j])
  return l


Ну и второй вариант osiev2 просто «чуть» быстрее, т.к. инициирует сито гораздо оптимальнее.
def primes_sieve(n):
  """ temporary odd direct sieve for primes < n """
  #sieve = list(range(3, n, 2))
  l = ((n-3)//2)
  sieve = [-1] * l
  for k in range(3, n, 2):
    o = (k-3)//2
    i = sieve[o]
    if i == -1:
      i = sieve[(k-3)//2] = k
    if i:
      f = (i*i-3) // 2
      if f >= l:
        break
      sieve[f::i] = [0] * -((f-l) // i)
  return sieve


Эти два метода можно было переделать на итеративное сито (например искать пары блочно по 10K или 100K). Это позволило бы значительно сэкономить память при подсчете. Например, если сейчас попробовать оба osieve варианта с 1G или 10G, мы практически гарантировано сразу получим MemoryError исключение (ну или вы богатый буратино — и у вас очень много памяти и 64-х битный питон :).

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

А на исходных 100K время исполнения последнего уже не возможно было подсчитать — 0.00 mils (я подсчитал его, только увеличив количество итераций исполнения times до 10).
В чем я практически уверен — это то, что увеличить скорость еще на один порядок вряд ли удастся, не только на scala, но и на чистом C. Если только снова алгоритмически…

Сам скрипт буде кто собирается поэкспериментировать, можно спросить помощь, например так:

sexy-primes-test.py --help


Если что, про простые числа довольно неплохо и очень подробно написано в wikihow.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Прототипное ООП для Lua

Привет, я придумал свой велосипед для реализации прототипного подхода ООП в Lua.

Основные фишки

  • Single inheritance
  • Traits
  • LuaJIT

Перейдем сразу к примерам.

-- подключаем модуль
local object = require("object")

-- определяем наш класс, который на самом деле объект
local HelloClass = object:extend(function(class)
  -- конструктор (необязательно)
  function class:init(name)
    self.name = name
  end

  -- метод класса
  function class:sayHello()
    print("Hello " .. self.name)
  end
end)

local hello = HelloClass:new("John")
hello:sayHello()



Как видим, вся магия заключается в методе extend(traits..., f), который расширяет текущий объект.

Можно определять переменные внутри

local object = require("object")
local Status = object:extend(function(status)
  status.HTTP_200_OK = {200, "OK"}
  status.HTTP_405_METHOD_NOT_ALLOWED = {404, "Method not allowed"}
end)

print(Status.HTTP_200_OK[2])

Статические методы

Куда же без них…
local object = require("object")
local MathUtils = object:extend(function(class)
 function class.square(x)
  return x * x
 end
end)

-- вызываем статический метод
print(MathUtils.square(10))

-- вызывает тот же метод но уже через инстанс
print(MathUtils:new().square(10)) -- 100

Конструктор

При создании нового экземпляра через new() вызывается конструктор init()
local Counter = object:extend(function(class)
   -- конструктор, который принимает какой-то параметр (может быть много параметров)
   function class:init(initial)
     self.ticks = initial or 0
   end

   function class:tick()
     self.ticks = self.ticks + 1
   end

   function class:getTicks()
     return self.ticks
   end
end)

local c = Counter:new()
c.tick()
c.tick()
print(c:getTicks() == 2)

Наследование и перегрузка методов

Как я упомянул, наследование сделано как single inheritance, то есть отнаследоваться можно только от одного «класса», однако есть еще трейты, о которых поговорим чуть позже. Перегрузка методов не вызывает никаких вопросов.
local Shape = object:extend(function(class)
  function class:getArea()
    return 0
  end
end)

local Square = Shape:extend(function(class)
  function class:init(side)
    self.side = side
  end

 -- перегружаем метод
  function class:getArea()
    return self.side * self.side
  end
end)

local sq = Square:new(10)
print("Area = " .. sq:getArea())

Вызов родительского метода

Для этого надо использовать второй параметр лямбда-функции, которую передаете в extend, которая есть ссылка на родительский объект (который хотим расширить)
local Foo = object:extend(function(class)
  function class:init(value)
    self.value = value
  end

  function class:say()
    print("Hello " .. self.value)
  end
end)

class Bar = Foo:extend(function(class, parent)
  function class:init(value)
    -- вызывает конструктор родителя
    parent.init(self, value)
   end
end)

local foo = Foo:new("World")
foo:say() -- напечатает "Hello World"

local bar = Bar:new("World")
bar:say() -- напечатает "Hello World"

Трейты

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

Просто передайте ваши трейты в начало аргументов extend()

local TraitX = function(trait)
  function trait:setX(x)
    self.x = x
    return self
  end
  function trait:getX()
    return self.x
  end
end

local A = object:extend(TraitX, function(class)
  function class:say()
    print(self.x)
  end
end)

A:new():setX(10):say()

Полезные функции

is_instanceof(self, instance) — вернет true, если instance является прямым или непрямым наследником self
local ClassA = object:extend()
local ClassB = object:extend()

local obj_a = ClassA:new()
local obj_b = ClassB:new()

print(obj_a:is_instanceof(ClassA)) -- true
print(obj_a:is_instanceof(object)) -- true
print(obj_a:is_instanceof(ClassB)) -- false

is_typeof(self, instance) — вернет true, если instance является прямым наследником self

local ClassA = object:extend()
local ClassB = object:extend()

local obj_a = ClassA:new()
local obj_b = ClassB:new()

print(obj_b:is_typeof(ClassA)) -- false
print(obj_b:is_typeof(ClassB)) -- true

LuaJIT

Как альтернатива, поддерживается работа в LuaJIT.
Где код, Карл?

Здесь

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Датчики и микроконтроллеры. Часть 1. Матчасть

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

Здание суда уже строят, значит пора кого-то вешать.


В этом цикле я расскажу о датчиках — как о немаловажном элементе системы управления неким объектом или тех. процессом.
Все свое повествование я буду вести касаемо практических вопросов реализации цифровых систем управления на базе микроконтроллеров.
Руководство не претендует на всеобщий обхват вопроса.
Хотя после того, как мой конспект перелез за 20 страниц текста, я решил разбить статью на следующие части:
  • Часть 1. Мат. часть. В ней мы рассмотрим датчик, не привязанный к какому-то конкретному измеряемому параметру. Рассмотрим передаточные функции и динамические характеристики датчика, разберемся с его возможными подключениями.
  • Часть 2. Датчики климат-контроля. В ней я рассмотрю особенности работы с датчиками температуры, влажности, давления и газового состава
  • Часть 3. Датчики электрических величин. В ней я коснусь измерения электрических параметров: напряжения, тока, мощности, частоты, коэффициента мощности и искажений


Введение



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

Рисунок 1. Типовая схема замкнутой системы регулирования
На рисунке 1 представлена типовая схема системы регулирования. Имеется сигнал задания , который сравнивается с сигналом на выходе, получаемым с помощью датчика, имеющего передаточную функцию Wд(p). Ошибка управления подается на регулятор, который, в свою очередь, формирует сигнал управления исполнительным узлом, формирующим выходной сигнал Y.[1]
Простой пример — центробежный регулятор частоты вращения двигателя, где датчиком является платформа с шарами, которая, вращаясь, устанавливает то или иное положение топливной рейки. Заслонка, управляемая этой рейкой, регулирует количество топлива, подаваемое на двигатель. Сигналом задания будет являться требуемое значение скорости.

1.1 Классификация датчиков


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

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

Ярким примером опять является терморезистор, сопротивление которого напрямую зависит только от температуры измеряемого объекта, и термопара, выходное напряжение которой зависит от разности температур между горячим и холодным концами.
При разработке радиоэлектронного оборудования важным фактором характеристик датчика также является характер выходного сигнала.
  • Аналоговые датчики на выходе имеют непрерывный выходной сигнал, для снятия которого необходимо использовать аналого-цифровой преобразователь, после чего необходимо произвести преобразования значения АЦП в формат измеряемой величины.
  • Цифровые датчики, информация с которых снимается с помощью различных цифровых интерфейсов. Как правило, информация доступна непосредственно в формате измеряемой величины и не требует проведения дополнительных преобразований.
  • Дискретные датчики, имеющие только два варианта сигнала на выходе канала датчика — лог 0. и лог. 1. Примером такого датчика является конечный выключатель, имеющий состояния замкнут и незамкнут. Дискретный датчик может иметь несколько выходных каналов, каждый из которых находится в одном из двух состояний. Например, 12-разрядный абсолютный датчик положения.
  • Импульсные датчики, формирующие импульсы выходного сигнала, амплитуда или длительность которых зависит от измеряемой величины. Например, инкрементальный датчик положения формирует на выходе код Грея. При этом, чем выше частота вращения вала датчика, тем большая частота сигнала будет на выходе, что позволит с высокой точностью определить частоту вращения вала.

2 Характеристики датчиков



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

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

При работе с датчиком требуется знать соотношение уровней сигналов на входе и выходе. Это соотношение, Y = f(X) будет представлять собой передаточную функцию и однозначно определять выходное состояние при определенном входном воздействии.
Передаточная функция может быть линейной и будет определяться как
(1)
Где a – наклон прямой, определяемый чувствительностью датчика и b – постоянная составляющая(т.е. уровень выходного сигнала при отсутствии сигнала на входе)

Рисунок 2. Линейная зависимость
Помимо датчиков с линейной зависимостью, могут быть датчики с логарифмической зависимостью, с передаточной функцией вида
(2)
Экспоненциальной:
(3)
Или степенной:
(4)
Где k – постоянное число.
Существуют датчики с более сложными передаточными функциями. Но на то есть документация.
Однако, помимо передаточной функции нужно понимать, какими свойствами обладает датчик в динамике, т. е. насколько быстро и точно отрабатывает датчик выходной сигнал при быстром изменении входной величины. Практически каждый реальный датчик имеет в себе накопитель энергии — конденсатор, массу и т. п. Рассмотрим поведение датчика, динамические характеристики которого описываются уравнением первого порядка:
(5)
В теории автоматического управления существует два тестовых входных сигнала. Это единичная функция — подача в нулевой момент времени единицы, и дельта-функция — подача сигнала бесконечной амплитуды и бесконечно малой длительности.

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

Рисунок 4. Реакция апериодического звена первого порядка на тестовые сигналы
Следует отметить, что значение на выходе датчика будет соответствовать поданному на входе только после завершения переходного процесса, которое будет длиться 3-4τ, где τ — постоянная времени нашего звена. При t=1τ, выходное значение достигнет

Нетрудно посчитать, что при t = 2τ выходное значение составит 86%, а при t = 3τ — 95% и переходный процесс будет считаться завершенным.
Таким образом нужно понимать, что, например, тот же датчик температуры будет реагировать на изменение температуры окружающей среды с некоторым запаздыванием из-за того, что между датчиком и окружающей средой имеется корпус, который должен поглотить тепло и нагреться. На это требуется время.
Разумеется, инерционные датчики могут описываться более сложными уравнениями, например представляться апериодическими звеньями второго порядка, иметь задержку реакции и т. д. Особенности поведения таких звеньев подробно описаны в [1].
2.3 Точность, нелинейность

Одной из важных характеристик датчика является его точность в диапазоне измеряемых величин. Выходной сигнал датчика соответствует значению измеряемой величины с некоторой достоверностью, называемой погрешностью.
Например, датчик температуры имеет точность ±2 градуса. Это означает, что при реальной температуре измеряемого объекта в 100 градусов, допустимые показания данного датчика температуры находятся в пределах 98 – 102 градусов.
Зачастую, это объясняется нелинейностью датчика в измеряемом диапазоне. В зависимости от текущего диапазона измерения, коэффициент наклона передаточной функции изменяется в некоторых пределах. При этом, в спецификации указываются либо кривые изменения точности по диапазону, либо худшие показатели нелинейности в том или ином диапазоне.
Кроме того, некоторые датчики имеют эффект гистерезиса, когда для одного и того же входного сигнала после возрастания и убывания значения выходного сигнала получаются разными. Типичной причиной гистерезиса является трение и структурные изменения материалов. Наибольшему эффекту гистерезиса подвержены датчики на основе ферромагнитных материалов.
Некоторые датчики требуют проведения калибровки для повышения точности. Для линейного датчика необходимо с заведомо известной точностью определить показания в двух точках, находящиеся на разных концах рабочего диапазона. Можно воспользоваться более точной аппаратурой, можно воспользоваться эталоном (например черное тело, эталонный килограмм и т. п.). Точность после калибровки естественно не сможет превышать точность эталона.
2.4 Чувствительность датчика, разрешающая способность и мертвая зона

Мертвая зона датчика — это нечувствительность датчика в определенном диапазоне входных сигналов. В пределах этой зоны выходные показания некорректны.
Для примера на рисунке 2 показания выходной величины для всех значений от 0 до x0 не определены. Такой особенностью грешат, например, некоторые датчики тока, имеющие нулевое напряжение на выходе при токах меньших, к примеру, 10мА.
Во всем остальном диапазоне имеет место определенная чувствительность датчика, т. е. насколько силен прирост выходного сигнала на изменение входного сигнала. т. е. чувствительность определяется следующей формулой:

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

3 Способ подключения датчиков



В зависимости от типа датчика, подключается он к измерительному тракту по разному.
Подключение пассивного датчика

Так как пассивный датчик без посторонней помощи в ответ на внешнее воздействие самостоятельно вырабатывает для нас электрический сигнал, нам этот сигнал нужно считать.
В зависимости от того, будет ли наш датчик источником тока или источником напряжения, способ подключения будет отличаться.
К примеру, термопара является источником напряжения — напряжение на выходе не зависит от величины выходного тока (в разумных пределах конечно). Наша задача — измерить вырабатываемую ЭДС. Так как измерительный тракт будет иметь некоторое конечное сопротивление, схема подключения будет следующей:

Рисунок 5. Подключение источника напряжения к АЦП
Если Radc будет много больше внутреннего сопротивления r, тогда падение напряжения на нем будет стремиться к нулю и напряжение на входе АЦП будет стремиться к значению ЭДС.
Во второй части я подробно рассмотрю термопару, как один из самых точных и быстродействующих датчиков.
Другой случай, если наш датчик является источником тока, т.е генерируемое им напряжение зависит от пропускаемого через нагрузку тока.
Подключение датчика аналогично:

Рисунок 6. Подключение источника тока к АЦП
Однако, сопротивление нагрузки источника тока теперь должно стремиться к нулю. Для этого, датчик шунтируется резистором необходимого сопротивления, превращая тем самым, источник тока в источник напряжения:

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

Наиболее яркий представить такого датчика — датчик тока.

ВНИМАНИЕ: датчики, имеющие схему замещения в виде источника тока, следует обязательно шунтировать сопротивлением и не допускать обрыва цепи шунтирования при наличии сколь угодно малого входного воздействия. В противном случае, тот же датчик тока генерирует на свободных клеммах вторичной обмотки напряжение в киловольты до пробоя схемы измерения или самого датчика. Современные датчики тока тестируют на напряжении 1кВ и более, так что получить на выходе 2-3кВ, а еще попасть в них пальцем — не самая сложная задача.


Подключение активного датчика

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

Рисунок 8. Подключение датчика к нерегулируемому источнику тока
Источник тока вырабатывает ток постоянного значения известной величины. Тогда, выходное напряжение будет определяться по формуле:
(7)
Например, рассчитаем выходное значение напряжения при токе источника 10мА если наш датчик изменяет сопротивление от 0,1кОм до 1 кОм. Тогда максимальное выходное напряжение будет равно
(8)
Что вполне соответствует требуемому значению напряжения для аналоговой системы управления на базе операционных усилителей.
Где взять источник тока? Бывает так что он встроен в сам микроконтроллер. Например в микроконтроллерах ADuCM360/361 есть два встроенных источника тока 0,01-1мА. Правда там у них диагностическая задача — подавая малый ток через цепи датчика можно убедить в его наличии и исправности.
Конечно, нам привычнее использовать источник напряжения с делителем:

Рисунок 9. Подключение датчика к источнику напряжения с делителем
Если говорить на чистоту, то цепочка U-R1 образует тот же самый источник тока, только его параметры зависят от нагрузки — . Напряжение на выходе будет определяться по следующей формуле:
(9)
И тут всплывает главная проблема такого метода — от сопротивления нашего датчика в знаменателе не избавишься никак и показания становятся нелинейными, в отличие, кстати, от первого варианта.
Встает вопрос — каким должно быть сопротивление R1? Оно должно обеспечивать максимальный диапазон выходного напряжения. т. е. при известных значениях минимального и максимального сопротивления датчика Rд1 и Rд2, abs(Uвых1 — Uвых2) -->max
С другой стороны, максимальное выходное напряжение у нас ограничено входными цепями измерительного устройства. Например, на вход микроконтроллера с питанием 5В необходимо подать напряжение, к примеру, не более 2,5В. Отмечу, что если максимально возможное напряжение, подаваемое на вход АЦП меньше напряжения питания, то мы сможем его туда подать.
Если наш датчик изменяет сопротивление от 0,1кОм до 1 кОм, то примем сопротивление резистора R1 равное верхней границе сопротивления датчика. Тогда Uвых сможет изменяться в пределах от 1/11Uвх до 1/2Uвх. В абсолютных цифрах данного примера — от 0,45 до 2,5В. И такими значениями мы используем (2,5-0,45)/2,5 = 82% всего диапазона АЦП, что довольно неплохо.

Еще датчик можно воткнуть в состав измерительного моста и измерять разницу напряжений в его плечах:

Рисунок 10. Датчик в составе измерительного моста
В этом случае мы работаем с дифференциальным АЦП, измеряя разность потенциалов Uab. Она будет равна:
(10)
Причем сопротивление резистора R1 может быть таким, чтобы Uab могло быть и отрицательным. Существуют датчики, внутренняя схема которых уже представляет собой балансный мост с необходимыми характеристиками. Позднее я рассмотрю примеры таких датчиков.

Существуют более удобные в использовании датчики. Они выдают необходимый аналоговый сигнал и без танцев с резисторами. Например, аналоговый датчик влажности HIH-4010-004 — трехвыводной корпус, 5В питание, линейный выход. Подключается это чудо так:

Рисунок 11. Подключение датчика влажности HIH-4010-004
Два провода к источнику опорного напряжения, выход — к АЦП микроконтроллера.

Подключение цифровых датчиков по стандарту 1-Wire

1-Wire это двунаправленныя низкоскоростная цифровая шина передачи данных, требующая всего два провода — информационный провод и землю. Шина достаточно проста в использовании, поддерживает паразитное питание устройств от линии и позволяет подключать параллельно множество однотипных устройств вроде датчиков температуры(всеми любимыми DS18B20), или микросхем идентификации (iButton).
Паразитное питание организовывается следующим образом:

Рисунок 12. Паразитное питание устройств шины 1-Wire
А это обычное активное питание устройства, когда до источника рукой подать.

Рисунок 13. Питание устройства 1-Wire от внешнего источника
Количество подключенных параллельно датчиков фактически ограничено лишь параметрами линии.
Возможно горячее подключение и идентификация на ходу. Причем вычислительная сложность алгоритма идентификации O(log n)
Более подробно с этим протоколом мы поработаем во второй части.
А пока, про сам протокол можно почитать по классической ссылке: http://ift.tt/1jcu96W
Подключение цифровых датчиков по стандарту I2C(Twi)/SMBus

Если 1-Wire требовала один провод данных, то эта шина, исходя из названия Two-Wire Bus — два.
Один из проводов — SCL будет тактирующим, по второму — SDA, полудуплексом будут передаваться данные.
Шина с открытым коллектором, следовательно обе линии необходимо подтянуть к питанию. Датчик будет подключаться следующим образом:

Рисунок 14. Подключение датчиков по I2C
Общее количество устройств, которые можно подключить к шине I2C — 112 устройств при 7-разрядной адресации. Каждому устройству на деле выделяется два последовательных адреса, младшим битом выставляется режим — на чтение или запись. Есть строгое требование по емкости шины — не более 400пФ.
Общеупотребительные значения скоростей — 100 кбит/сек и 10 кбит/сек, хотя последние стандарты допускают и скоростные режимы в 400 кбит/сек и 3.4мбит/сек.
Шина может работать как с несменяемым мастером, там и с передачей флага.
Огромное количество информации по протоколу можно найти по этой ссылке: http://ift.tt/1HXYCmL
Подключение цифровых датчиков по стандарту SPI

Требует как минимум три провода, работает в режиме полного дуплекса — т.е. организует одновременную передачу данных в обе стороны.
Линии связи:
  • CLK — линия тактового сигнала.
  • MOSI — выход мастера, вход слейва
  • MISO — вход мастера, выход слейва
  • CS — выбор чипа (опционально).

Одно из устройств выбирается мастером. Оно будет отвечать за тактирование шины. Подключение осуществляется перекрестным образом:

Рисунок 15. подключение по SPI и суть передачи
Каждое устройство в цепи содержит свой сдвиговый регистр данных. С помощью сигналов тактирования, спустя 8 тактов содержимое регистров меняется местами, тем самым, осуществляя обмен данными.
SPI — Самый скоростной из представленных интерфейс передачи данных. В зависимости от максимально-возможных частот тактирования скорость передачи данных может составлять 20, 40, 75 мбит/сек и выше.
Шина SPI позволяет подключать устройства параллельно, но здесь возникает проблема — каждому устройству требуется своя линия CS до процессора. Это ограничивает общее количество устройств на одном интерфейсе.
Главная сложность в настройке SPI — это установить полярность сигнала тактирования. Серьезно. Настроить SPI не просто, а очень просто.
Коротко и ясно об SPI с описанием периферийных модулей SPI для AVR и MSP430 можно прочитать здесь http://ift.tt/1HXYCmO

4 Снятие показаний с датчиков



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

Рисунок 16. Процесс считывания показаний с датчика
Рассмотрим каждый вариант по отдельности и набросаем скелеты:
Вариант 1. запустили режим измерений, подождали, считали.
Вариант притягателен своей простотой, однако за ней кроется проблема — во время ожидания выполнения измерений микроконтроллер нагло простаивает, не выполняя задач. В большинстве систем автоматики такой режим — непозволительная роскошь.
В коде это будет выглядеть следующим образом:
Sensor.Start();//запустить процесс измерений
delay(MINIMAL_SENSOR_DELAY_TIME);//ожидаем завершения процесса
int var = Sensor.Read();//считываем данные


Вариант 2. запустили режим измерений, вернулись к другим задачам, по прошествии времени сработало прерывание, считали данные.
Один из лучших вариантов. Но наиболее сложный:
void Setup(){
TimerIsr.Setup(MINIMAL_SENSOR_DELAY_TIME);//настраиваем прерывание по таймеру с необходимой периодичностью
int mode = START;//переменная состояния
Sensor.Start();//запускаем процесс измерений в первый раз
}

TimerIsr.Vector(){//обработчик прерывания по таймеру
if (mode == START{
mode = READ;
var = Sensor.Read();//если датчик был в режиме измерения, считываем данные
}
else
{
mode = START;
Sensor.Start();///если датчик был в режиме считывания данных, запускаем новый цикл измерений
}
}


Выглядит неплохо. позволяет варьировать время между циклами измерений и циклами считывания. например, датчик состава газов должен успеть остыть после предыдущих измерений, либо успеть нагреться во время измерений. Это разные периоды времени.
Вариант 3: Считали данные, запустили новый виток.
Если датчик позволяет после считывания данных запускать новый цикл измерений, то почему бы и нет — сделаем все наоборот.
void Setup(){
TimerIsr.Setup(MINIMAL_SENSOR_DELAY_TIME);//настраиваем прерывание по таймеру с необходимой периодичностью
Sensor.Start();//запускаем процесс измерений в первый раз
}
TimerIsr.Vector(){//обработчик прерывания по таймеру
var = Sensor.Read();//считываем данные
Sensor.Start();///запускаем новый цикл измерений


Отличный способ сэкономить время. и знаете что — такой метод отлично работает и без прерываний. Цифровые датчики хранят вычисленное значение вплоть до отключения питания.А с учетом того, что считывать сигналы с датчика влажности ввиду его инерционности в 15 секунд часто и не требуется, можно и вовсе сделать так:
void Setup(){
Sensor.Start();//запускаем процесс измерений в первый раз

while(1){
//много всякой остальной рутины
var = Sensor.Read();//считываем данные
Sensor.Start();///запускаем новый цикл измерений
}
}


К сожалению, первый метод поголовно используется в библиотеках и примерах для Arduino, не позволяет этой платформе правильно использовать ресурсы микроконтроллера. Зато он проще в написании и отладке.
4.1 Работа с АЦП

Имея дело с аналоговыми датчиками имеем дело с АЦП. В данном случае рассматривается АЦП встроенный в микроконтроллер. Так как АЦП является по сути тем же датчиком — преобразует электрический сигнал в информационный — для него справедливо все что описано выше в разделе 2. Главными характеристиками АЦП для нас являются его разрядность, опорное напряжение и быстродействие. При этом, выходным значением АЦП преобразования будет некоторое число, которое необходимо перевести в абсолютное значение в единицах измеряемой величины. Ниже, для отдельных датчиков будут рассмотрены примеры таких расчетов.
4.1.1 Опорное напряжение
Опорное напряжение АЦП — это напряжение, которому будет соответствовать максимальное выходное значение АЦП. Опорное напряжение подается от источника напряжения, как встроенного в микроконтроллер, так и внешнего. От точности этого источника зависит точность показаний АЦП. Типовое опорное напряжение встроенного источника равняется напряжению питания или половине напряжения питания микроконтроллера. Могут быть и другие значения.
4.1.2 Разрядность АЦП и чувствительность
От разрядности АЦП зависит его чувствительность. Чем больше промежуточных ступеней выходного напряжения, тем выше будет чувствительность.
Допустим, опорное напряжение АЦП Uоп. Тогда, N-разрядный датчик, имея 2N возможных значений, имеет чувствительность
(11)
Таким образом, для 12-разрядного АЦП и опорного напряжения в 3,3В его чувствительность составит 3,3/4096 = 0,8мВ
Так как наш датчик также обладает определенной чувствительностью и точностью, будет неплохо, если АЦП будет обладать лучшими показателями.
4.1.3 Быстродействие АЦП
Быстродействие АЦП определяет, насколько быстро могут быть получены показания. АЦП последовательного приближения требуется определенное количество тактов, чтобы снять показания. Чем больше разрядность, тем больше тактов и меньше. Быстродействие АЦП измеряется в количестве семплов данных в секунду. Для каждого варианта разрядности возможно рассчитать свое быстродействие. В технической документации обычно указывается диапазон минимального-максимального быстродействия при максимальной частоте тактирования АЦП.
4.2 Цифровые датчики

Главное преимущество цифровых датчиков перед аналоговыми — они предоставляют информацию об измеряемой величие в готовом виде. Цифровой датчик влажности вернет абсолютное значение влажности в процентах, цифровой датчик температуры — значение температуры в градусах.
Управление датчиком осуществляется с помощью имеющихся в нем регистром в форме вопрос-ответ. Вопросы следующие:
  • Запиши в регистр A значение B
  • Верни значение, хранящееся в регистре C

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

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

Список полезной литературы:


  1. Бессекерский В.А., Попов Е.П. Теория систем автоматического управления / В.А. Бесссекерский, Е.П. Попов — Изд. 4-е, перераб. И доп. — Спб., Профессия, 2007. — 752с.
  2. Датчики: Справочное пособие / В.М. Шарапов, Е.С. Полищук, Н.Д. Кошевой, Г.Г. Ишанин, И.Г. Минаев, А.С. Совлуков. — Москва: Техносфера, 2012. — 624 с.
  3. Г. Виглеб. Датчики. Устройство и применение. Москва. Издательство «Мир», 1989
  4. Современные датчики. Справочник. ДЖ. ФРАЙДЕН Перевод с английского Ю. А. Заболотной под редакцией Е. Л. Свинцова ТЕХНОСФЕРА Москва Техносфера-2005

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.