четверг, 23 декабря 2010 г.

Эвристика в поиске пути

Когда наша команда впервые столкнулась с задачей поиска пути, мы не смогли удержаться от попытки изобрести собственный "велосипед". Путь был тупиковым, что стало ясно уже через несколько недель экспериментов и поиск пути отложили почти на год. И вот через год задачу снова подняли и решили использовать обычный A*. Его описаний в интернете достаточно и в 99% случаев достаточно просто реализовать алгоритм по шаблону. В моем случае именно так и получилось, поиск пути занял свое место в Runserver.Math и в серверах на его основе. Через несколько месяцев появились сообщения, что траектория выходит не очень красивой - агенты довольно неестественно движутся под углами, кратными 45-ти градусам. Через некоторое время мне встретился сайт тов. Amit Pate с описанием и примерами эвристической функции. Вчитавшись я осознал, что в мой код прокралась критическая ошибка..


Теория

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

Манхэттенское расстояние

Достаточно часто используется т.н. Манхэттенский метод, который вычисляет минимальное расстояние, которое надо пройти вдоль осей координат, чтобы попасть в данную точку:
h = D * (|x-fx| + |y-fy|)

x, y - текущие координаты, fx, fy - координаты конечной точки пути, D - вес одного шага.
Главный недостаток этого алгоритма - "ступенчатость" траектории.

Диагональное расстояние

Более сложная разновидность Манхэттенской функции учитывает движение по диагонали между клетками. Формула учитывает, вдоль какой из осей путь будет длиннее:
ax = |x-fx|
ay = |y-fy|
if ax > ay then
h = ax * D * √2 + D * (ax - ay)
else
h = ay * D * √2 + D * (ay - ax)

D - вес шага вдоль осей координат, D * √2 - вес шага по диагонали. Такая функция идеально сбалансирована и не смотря на большое количество исследованных точек, выдает оптимальный путь за приемлимое время.

Евклидовое расстояние

Другой подход - использовать реальное расстояние до конечной точки. В этом случае функция получается не идеально сбалансированной, потому что расстояние g считается с учетом движения в 8-ми направлениях, а от точки до конца пути - напрямик. A* все-равно выдаст оптимальный путь, но проверит чуть большее количество точек:
         _________________
h = D * √(x-fx)² + (y-fy)²


Квадрат евклидового расстояния

Этот метод во многих источниках заклеймен как лженаучный и неверный. Проблема в том, что значение функции будет заметно больше пройденного пути g, потому алгоритм будет искать не оптимальный путь, а как-бы "притягиваться" к конечной точке. Формула выглядит так:
h = D * ((x-fx)² + (y-fy)²)

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

Ситуация усложняется при добавлении препятствий. Квадратичная функция:

Диагональная функция:

Во втором случае путь "правильнее", но было проверено очень много лишних точек. По-честному, первый вариант вообще не является A* - он выдает не самый оптимальный путь, а первый найденный. Меня такой вариант устраивал - в реальной жизни персонажи редко движутся идеально, потому для AI такой алгоритм вполне подходит. Нерешенной осталась только проблема, из-за которой я и начал копаться в эвристике - излишняя "геометричность" пути.

Алгоритм компаса

Я не придумал, как правильно сформулировать название этого алгоритма. Автор алгоритма (Amit Patel) описал его так:
A different way to break ties is to prefer paths that are along the straight line from the starting point to the goal

Идея схожа с навигацией по компасу - имея некое направление, после обхода препятствия надо двигаться в том же направлении, что и раньше. Базовая формула эвристики остается прежней, но к ней добавляется еще небольшое смещение:
cross = |(x-fx)*(y-sy) - (y-fy)*(x-sx)|
h = h + cross * k

sx, sy - координаты начальной точки, k - коэффециент смещения, у автора алгоритма 0.001, cross - модуль векторного произведения вектора движения для текущей и начальной точки.
Для открытых пространств такая функция работает очень хорошо, а вот обход препятствий дает некоторую погрешность, которой можно управлять, меняя значение k. Я так и не нашел баланса этого коэффициента, при котором путь остается оптимальным и не появляется артефакт "возврата":


Алгоритм "наведения"

В результате всех экспериментов я вывел собственный алгоритм, схожий с "компасным", но стремящийся не к линии между начальной и конечной точкой, а к линии между предыдущей пройденой и конечной точкой:
cross = |(x-fx)*(y-py) - (y-fy)*(x-px)|
h = h + cross * k
px, py - координаты предыдущей пройденной точки. Такой подход дает не идеальную картину при движении без препятствий, зато при коэффициенте k = 0.5 обход препятствий смотрится вполне корректно:

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

"Жадный" алгоритм

Результатом дальнейших поисков стала функция, напрочь отрицающая баланс g и h. Это сделало алгоритм из A* явно выраженный Greed Search, который, как ни странно, работает очень быстро и для AI выглядит вполне естественно.
Формула такова:
ax = |x-fx|
ay = |y-fy|
if ax > ay then
h = ax * D * n
else
h = ay * D * n
cross = |(x-fx)*(y-sy) - (y-fy)*(x-sx)|
h = h + cross * k
n - весовой фактор, k - коэффициент "наведения".
В приведенной иллюстрации коэффициенты равны 100 и 1 соответственно.

Заключение

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

P.S. Напоследок несколько "живых" примеров работы Greed алгоритма.

Средняя плотность. Расчет занял 228мс, 2689 точек, 5289 проверок видимости:

Большая плотность. Расчет занял 274мс, 2177 точек, 4110 проверок видимости:


Дальше..

суббота, 27 ноября 2010 г.

Как сделать невозможное?

Ответ на вопрос прост - не останавливаться, какой бы сложной не была задача. Даже если все вокруг говорят, что это невозможно.
Моя задача была заменить драйвер устройства в Linux, вшитый намертво в ядро. Были бы исходники этого ядра - все решалось бы сравнительно просто, но в нашем случае (ядро читалки Nook) исходники были не рабочие и годичной давности. На x86 я бы дизассемблировал место инициализации драйвера в ядре и забил NOPами, но тут уже ARM архитектура и ядро в zImage..

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

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

Затем начались эксперименты на уровне исходников. Мое внимание привлек такой код:

static int __devinit synaptics_ts_init(void)
{
synaptics_wq = create_singlethread_workqueue("synaptics_wq");
if (!synaptics_wq)
return -ENOMEM;
return i2c_add_driver(&synaptics_ts_driver);
}

static void __exit synaptics_ts_exit(void)
{
i2c_del_driver(&synaptics_ts_driver);
if (synaptics_wq)
destroy_workqueue(synaptics_wq);
}

Если существует функция i2c_del_driver для выгрузки драйвера, то почему нельзя вызвать ее из своего модуля, чтобы выгрузить чужой? К сожалению, в ядре Linux есть ситуации, когда не имея указателя никак нельзя обратиться к обьекту. Например, метод destroy_workqueue можно вызывать только с указателем очереди, а он есть лишь у того, кто эту очередь создал и без получить его малореально - никаких find_workqueue в природе нет.

В нашем же случае шанс был - пусть и i2c не позволяет искать драйвер по имени, но по коду i2c-core.c стало понятно, что используются низкоуровневые вызовы device_register/device_unregister из linux/device.h. Там же нашлась функция driver_find, которая ищет драйвер по имени и идентификатору шины. Имя встроенного драйвера известно, а шина используется i2c и ее идентификатор в переменной i2c_bus_type:

struct device_driver * other;

other = driver_find(SYNAPTICS_I2C_RMI_NAME, &i2c_bus_type);

if (other)
{
printk("Previous driver found: %s\n", other->name);
return -ENOMEM;
}

Этот код корректно находит предыдущий драйвер и выводит его имя. Конечно же, этого было мало, потому я добавил driver_unregister(other) и получил Kernel Panic :)
Логично предположить, что раз мы регистрируем драйвер через i2c_add_driver, то и удалять его надо через i2c_del_driver, а не напрямую. Из описания структуры i2c_driver видно, что она содержит device_driver, которая и возвращается функцией driver_find. Для преобразования из указателя на вложенную структуру к родительской есть несколько подходов, но проще всего использовать стандартную конверсию to_i2c_driver. Получился вот такой код:

struct i2c_driver * otherDriver;
struct device_driver * other;

other = driver_find(SYNAPTICS_I2C_RMI_NAME, &i2c_bus_type);

if (other)
{
otherDriver = to_i2c_driver(other);
printk(KERN_ERR "Previous driver found: %s, addr 0x%x, owner %x\n", other->name, (int)otherDriver, (int)other->owner);
i2c_del_driver(otherDriver);
}

Что характерно, он тоже приводит к Kernel Panic. На этом этапе я уже было решил, что дерегистрация невозможна, но случайно заметил в drivers/base/core.c, что после вызова driver_find обычно вызывается функция put_driver. Оказалось, что у драйверов, как обектов ядра, есть интрузивный подсчет ссылок и после driver_find счетчик увеличивается на единицу, что не дает выгрузить драйвер во время i2c_del_driver. Добавление этого вызова поставило все на свои места и встроенный драйвер стал корректно выгружаться.

Конечно, сразу все не заработало, т.к. еще существовала workqueue с таким же именем, да и встроенный драйвер оказался "нечист на руку" - не удалял sysfs файлы при выгрузке, но это уже все было решаемо.

Результатом этих "танцев с бубном" стал собственный драйвер тачскрина для Nook с поддержкой Multitouch. Подробнее о самом драйвере можно почитать по этим ссылкам:
http://nookdevs.com/Multitouch
http://www.the-ebook.org/forum/viewtopic.php?t=16728

Дальше..

вторник, 23 ноября 2010 г.

Книжкая полка для Nook

Некоторое время назад я написал для Nook простенький менеджер файлов, без возможности удаления, копирования и пр. Потом этот браузер научился фильтровать файлы по типу, а затем и извлекать описания из книг, показывать обложки и пр. Сейчас это полноценная книжкая полка с Cover Flow (листанием обложек), которая при необходимости показывает все файлы устройства, позволяет устанавливать программы, хранит список последних книг.

Вот небольше видео, как это работает:




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

Пара скриншотов:





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

При выходе из программы сохраняется последняя выбранная папка, а каждый открытый документ сохраняется в виртуальную папку "Последние документы".
Заодно, программа позволяет выбрать .apk файл и установить его. Протестирована совместимость с встроеными ридерами epub/pdf/pdb файлов, а также с портом FBReader от mynook. Из файлов epub/fb2/fb2.zip извлекаются данные об авторе и названии книги, а также о ее серии. Открытые через программу книги затем корректно открываются через Reading Now. Также в программе есть список последних 9ти открытых документов и режим листания обложек (Cover Flow). Можно прятать выбраный файл, после чего он будет показываться только в режиме "Просмотр скрытых файлов". Также есть возможность просмотра изображений в форматах PNG и JPEG.

В данный момент стабильная версия программы имеет номер 1.2. Это значит, что в ней реализовано все, что задумывалось изначально, а также некоторые другие возможности вроде просмотра картинок, иконок для папок и пр. Полка работает под любыми версиями Android от 1.5 до 2.2, но в основном расчитана под экран Nook разрешением 600х944.

Программа доступна в двух версиях - как отдельное приложение и как замена B&N Library. При запуске в виде замены B&N Library пользователя спросят, какую библиотеку запустить - собственную или оригинальную. При использовании патченного framework-res.apk можно выбрать галочку "использовать эту программу постоянно".

Программа в виде замены Library

Ссылка: http://runserver.net/nook/nookFileBrowser.apk
Размер: 133593
md5: 3b4906752f89859f17de4ac55e2e385d

Отдельное приложение:

Ссылка: http://runserver.net/nook/nookFileBrowser_standalone.apk
Размер: 133573
md5: d04bfe255d19f751af3c4f7d981065aa

Дальше..

вторник, 19 октября 2010 г.

Создание патча из двух директорий

Задача сравнения двух директорий возникает более-менее часто и стандартные diff+patch под Unix позволяют с ней справиться довольно хорошо, но в моем случае надо было сделать именно архив изменений. На C++/C# программу можно было бы написать за несколько минут, но я задался целью использовать полноценное Unix решение.

Сначала я довольно долго ковырялся с diff, KDiff3 и похожими программами, но результат был очень далек от поставленной задачи, потому было решено писать .sh скрипт. Я совсем не Unix/Linux гуру, потому каждый шаг сопровождался длительным гуглением. :)

Список файлов

Для начала надо было получить списки. Вариации команды lr -R выдает нужные файлы, но в неудачном виде и их надо обрабатывать. Дойдя до вида ls -lR|tr -s ' '|cut -d ' ' -f 9, я решил, что терпение закончилось, плюнул на ls и использовал find. У этой команды недостаток в том, что к каждому файлу в добавляется относительный путь. Этого можно избежать, если сначала зайти в папку и делать find ., но тогда по непонятной причине из списка пропадают симлинки, причем использование параметра -type fl не помогает. Нормальным решением оказалось обрезание "лишнего" пути через sed.
find $2 | sed -e "s:^$2/::" > files.txt

Перебор и сравнение

Я решил перебирать все файлы из второй папки и проверять, есть ли они в первой. Довольно простой цикл с вызовом cmp:
for f in $(cat files.txt)
do
if [ -f "$2/$f" ]
then
if ! cmp -s "$1/$f" "$2/$f"; then
echo $f >> toadd.txt
fi
fi
done
Проверка [ -f "$2/$f" ] нужна, чтобы отсеять директории. Если файл не существует по пути "$1/$f", то он тоже попадает в список, что меня вполне устроило.

Архив

Полученный список toadd.txt скармливается команде tar. Чтобы пути в архиве были корректными, приходится делать дополнительный cd:
cd $2
tar -czvf ../result.tar.gz --files-from ../toadd.txt
cd ..

Эпилог

В результате потраченного часа времени, у меня теперь есть утилита, позволяющая сравнить, к примеру, две прошивки для какого-то устройства, разные версии репозитариев и пр., а на выходе получить tar.gz (или любой другой) архив с этими отличиями. Конечно, использование diff и patch дало бы гораздо меньший размер, но зато полученный результат гораздо прозрачнее и легче в использовании. Из заметных недостатков этого решения - в архив не попадут пустые директории.
Полный файл скрипта: http://runserver.net/temp/ddiff.sh

Дальше..

суббота, 16 октября 2010 г.

Рутинг Nook любой версии

Камрад cdump нашел метод записать произвольный файл на нук любой верии, в т.ч. и 1.4.1/1.4.2, которые ранее считались не рутабельными. Это значит, что реально "руссифицировать", т.е. залить свои программы на любое устройство. Детальное описание есть на сайте mynook.ru, а я же попробую описать как именно это делать в домашних условиях.

Подмена данных

Для рутинга нужно иметь WiFi сеть и доступ к интернету из нее. По адресу 217.20.163.111 я разместил собственную реализацию скриптов, которые имитируют апдейт от B&N. Достаточно сделать так, чтобы при проверке обновлений устройство обратилось к этому серверу вместо sync.barnesandnoble.com и edmfiletransfer.barnesandnoble.com.

Настройка под Windows

Под Windows мы не полезем в дебри серверных Routing Services, а воспользуемся программой TFTPD. Она может работать одновременно как DHCP и DNS сервер.

DHCP

Если у Вас есть возможность прописать сервер в настройках DHCP на роутере - эту чаcть можно пропустить и перейти к настройке DNS. Операция очень проста - запускаем TFTPD, нажимаем Settings, включаем DHCP Server и на закладке DHCP настраиваем примерно как на скриншоте. В IP Pool Starting Address пишем свободный адрес в Вашей сети, в Size of pool число больше 0, в WINS/DNS Server - адрес своего компьютера, в Default router - адрес шлюза.
Если все сделано верно, то Nook при следующем подключении к WiFi выберет IP адрес из указанного пула.

DNS

Для DNS сервера используем тот же TFTPD. Настроек в программе нет, достаточно только включить галочку DNS Server. Затем надо подправить файл hosts. Находится он обычно в папке Windows\System32\Drivers\etc\hosts. В конец файла надо дописать такие две строки:
217.20.163.111 sync.barnesandnoble.com
217.20.163.111 edmfiletransfer.barnesandnoble.com


Настройка для Linux/Unix/MacOS X

Пользователи Linux/Unix/MacOS X могут сами добавить в DNS сервер, например BIND. Если Вы не знаете, как это делается - лучше найдите компьютер с Windows. Пример записи в named.conf:
zone "barnesandnoble.com" {
type master;
file "named.bn";
};


Файл named.bn:
$TTL    86400
@ IN SOA barnesandnoble.com. root.barnesandnoble.com. (
2 ; Serial
28800 ; Refresh
14400 ; Retry
3600000 ; Expire
86400 ) ; Minimum
@ IN NS barnesandnoble.com.
@ IN A 217.20.163.111
* IN A 217.20.163.111
@ IN AAAA ::1


Процедура рутинга

Дальнейшая процедура рутинга довольно проста - надо убедить устройство проверить наличие обновлений. У меня это получилось только после регистрации устройства, через My Library. Причем, регистрацию надо выполнить с нормальным DNS сервером, а не с подменой. После этого нажатие на Check for new B&N Content привело к появлению записи Don't Blink от 29го сентября (физически эта запись считывается с моего сервера, а не с B&N) и затем началась загрузка обновления, сразу же закончившаяся ошибкой Error downloading update. Ошибка тут вполне нормальна, никаких проблем с этим нет. После выключения WiFi будет выполнен собственный скрипт, который и рутнет устройство - запустит adbd.

Что дальше?

Имея запущенный adbd, можно подключаться к устройству через adb по WiFi и делать с ним что-угодно. Если Вам это ни о чем не говорит или не хочется разбираться с adb и установкой программ вручную, есть альтернативный вариант. В скрипте кроме вызова adbd я добавил еще и выполнение некого файла root.sh. Файл должен лежать на встроенной карте рядом с папками my documents и другими. Без особых проблем можно сделать, чтобы этот файл устанавливал нужные программы, менял настройки или вообще приводил систему к виду прошивки Mynook.ru. Именно такой пакет доступен по ссылке ниже - он сделан на основе сравнения двух прошивок и записывает все недостающие файлы.
Для примера я сделал пакет, который делает следующие действия:
  • устанавливает лаунчер от Mynook.ru;
  • устанавливает библиотеку Nookdevs;
  • устанавливает NookFileManager;
  • устанавливает FBReader;
  • заменяет Home.apk пропатченой версией от Mynook;
  • заменяет Browser.apk пропатченой версией;
  • удаляет FirmwareUpdateService.apk;
  • записывает корректный wifi_stop.sh;
  • устанавливает busybox;
  • разрешает установку сторонних программ;
  • включает запуск adbd при старте;
Пакет доступен по этой ссылке: http://runserver.net/nook/mynook_package.zip
Для установки перед рутингом подключите Nook по USB и разверните содержимое архива (3 файла) в корень главного диска устройства (рядом с папками my documents и др). При рутинге после выключения WiFi подождите некоторое время и устройство само перезагрузится. После запуска у Вас будет альтернативный лаунчер, книжная полка с поддержкой FB2 и возможность устанавливать программы через NookFileManager.

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

Я же на днях выложу аналогичный пакет с пропатчеными мной оригинальными программами (подробнее о моих патчах в этой статье: http://blog.runserver.net/2010/10/nook.html).

Update: пакет программ заменен. теперь это полная копия прошивки 1.5.1 от Mynook.ru

Дальше..

пятница, 15 октября 2010 г.

Не канонический взгляд на Nook

Предыстория


Мое общение с электронными книгами началось в 2006м году с LBook V8; этим ридером я пользуюсь и по сей день, не смотря на разваливающий корпус и темноватый экран. Когда же товарищ попросил совета по выбору читалки, оказалось, что аналогичные PocketBook, Sony и пр. стоят чуть ли не больше, чем было уплачено тогда, а изменился по-сути только экран. Бонусы вроде "более быстрое листание" или "поддержка формата CHM" на мой взгляд тоже того не стоят. На этом фоне B&N Nook за $149+доставка показался чуть ли не даром богов :) Погуглив несколько дней я убедился, что устройство действительно уникально, а если и есть нюансы, то прошивка от Nookdevs или русская от Mynook.ru позволит их рано или поздно решить.
Устройство с EBay доставили за неделю, а вот с перепрошивкой не сложилось - именно эта серия устройств пока что не рутабельна. Зато оказалось, что заводская прошивка нормально браузит русские сайты и читает EPUB книги с встроенными шрифтами. О дополнительных программах можно забыть, но именно читать книги можно без проблем. В целом уствойство очень напомнило продукцию Apple - белое исполнение, удачный дизайн корпуса и п/о, минимум доступных настроек.



Второй ридер я уже брал для себя, с гарантированной возможностью перепрошивки - захотелось изучить Андроид изнутри, попробовать написать пару программ, может даже разобраться с взломом непрошиваемых устройств. За это пришлось переплатить, но в результате я стал обладателем перепрошиваемого Nook с 3G, потратив почти в полтора раза меньше, чем на "отечественные" аналоги. Тут и закончились первоначальные восторги и начались суровые будни. :)

Альтернативные прошивки


Для начала я залил прошивку 2.4.1 от Nookdevs: http://nookdevs.com/Softroot
Приятный интерфейс домашнего экрана сменился на самописный лаунчер, появилась альтернативная книжная полка и браузер. Рискую начать холивар, но все эти программы показались гораздо ниже качеством, чем оригинальные.. Работать стало откровенно неприятно, полезли баги. Возможность ставить дополнительные программы хороша, но адаптированных под Nook их отковенно мало, а качество тоже не блещет.

Вторым заходом была залита прошивка 1.5.1 от MyNook.ru: http://mynook.ru/firmware/
На устройстве появился еще один собственный лаунчер, FBReader и часть программ от nookdevs. Общее впечатление стало получше, но все-равно привкус кустарщины остался.. Русской экранной клавиатурой пользовался один раз при написании письма, а FB2 файлы по скорости и качеству читаются точно так же, как и EPUB, но навигация чуть менее удобна.

По-честному, на этом этапе надо было либо вернуться к оригинакльной прошивке, или остаться на русской, но.. как говорится, у меня "був час та натхнення". :)

Собственная прошивка


На устройстве оказался классический набор - Linux 2.6.27 + Android 1.5 Cupcake, предположительно Revision 3. Сама процедура прошивки реализована довольно добротно, с RSA подписью от SHA-256 хеша тела апдейта и только баг в самых первых прошивках позволяет рутнуть устройство через даунгрейд и без вскрытия. Поискав для приличия другие варианты взлома, я убедился, что основные дыры закрыты достаточно хорошо, а заодно получил некоторые навыки декомпиляции и повторной сборки Android программ.
Для собственных нужд была сделана собственная копия официальной прошивки 1.4.0 с одним только изменением - включен автозапуск adbd в /init.rc. После перепрошивки мы получаем 1 в 1 оригинальное устройство, но с доступом через adb, а значит и с возможностью устанавливать/удалять программы, ковыряться в системных настройках и пр.

Программы


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

Лаунчер


Через adb можно ставить программы, но запускать их проблематично - это нужно делать либо через adb, либо через самописные лаунчеры, от которых и я бежал. :)
Решение пришло в виде программы NookAppManager, которая не отягощена лишним интерфейсом и может запустить или удалить любую из установленных программ. Осталось решить, как запускать именно ее саму. На данный момент я не придумал ничего лучше, как перенаправить одну из дефолтных иконок в оригинальном лаунчере. Немного ковыряния в коде, backsmali + smali, и иконка шахмат стала моим бекдором для запуска чего-угодно и как-угодно. Решение не элегантно, но зато в повседневной жизни можно пользоваться стандартным интерфейсом и программами, а если нужен сторонний софт или шахматы - запускать AppManager и уже из него что-то еще.
На данный момент написана версия домашнего экрана, которая вместо папки Games делает папку Apps и показывает там все установленые приложения.

Браузер


К браузеру на ридере требования всего два: он должен браузить и качать файлы. Оригинальный браузер из прошивки 1.4.0 довольно хорош, но файлы не качает. Продукт от Nookdevs файлы качает, но заметно менее удобен и давно не обновлялся. А по-честному, он удовлетворяет только второму требованию. :) Заглянув в код оригинального браузера, я с удивлением обнаружил некие наработки, а главное UI для скачивания файлов. Несколько дней ушло на то, чтобы разобраться в том, как оно должно и могло бы работать, а затем на то, чтобы реализовать недостающие части, но в результате мы получили то, что хотели -удобный браузер с поддержкой скачивания.

Ридер RSS


На форумах для чтения фидов на устройстве рекомендуют использовать либо веб-аггрегаторы, либо адаптированный Trook. Последняя программа довольно неплоха, но меня не впечатлила, да и аггрегаторы как-то не пришлись по душе. В стандартный набор входит программа The Daily, которая в идеале должна читать новости с сайта Barnes & Noble, но на самом деле читает несколько малополезных фидов и русскоязычными пользователями не используется вообще. Первая версия моей модификации использовала оригинальный формат фидов и php транслятор на внешнем сервере, но затем у меня получилось полностью переписать загрузку фидов и теперь The Daily стал полноценным RSS ридером, а список фидов читается из файла feeds.xml на встроенной карте. У него есть заметные недостатки, например фиды читаются целиком при первом запуске, что занимает некоторое время, да и Atom не поддерживается, но для большей части фидов он отлично подходит.

Утилиты и сторонние программы


Кроме уже упомянутого Nook App Manager, довольно полезными оказались Nook Task Manager, NookTerm и Nook WiFi Locker. Теперь после перепрошивки устройства (бывает необходимо после экспериментов) я запускаю простенький .bat файл, который устанавливает эти утилиты, заменяет модифицированные мной программы и применяет некоторые оптимизации.
Что интересно, на читалку можно поставить почти любую Android программу, но для управления ей надо будет запустить VNC сервер или переназначить клавиши управления. Это дает надежду, что рано или поздно мы найдем метод управлять такими программами без VNC, а для самых полезных будут сделаны собственные порты под это устройство. К примеру, большие надежды возлагаются на CoolReader, автор которого ознакомился с реалиями нашего устройства и планирует его поддержку в скором времени.

Оптимизация


Дабы заряд тратился не так быстро, довольно полезно бывает убрать неиспользуемые сервисы. Сейчас сообщество на форуме The Ebook активно изучает, что можно безболезненно отключить, дабы продлить срок жизни ридера, но гарантированно безопасно только отключение FirmwareUpdateService. Деинсталировать его не получится, потому кардинальное решение - удалить:
adb shell rm /system/app/FirmwareUpdateService.apk

Также можно удалить SyncService.apk и ContactsProvider.apk, но тут уже могут быть нюансы вроде нерабочести покупки в официальном магазине B&N и пр.
Другое направление оптимизации - применение патчей для самого Android. На данный момент я пропатчил LocationManager и KeyInputQueue в файле services.jar, но еще нет статистики, насколько это помогло и помогло ли вообще.

Эпилог


На данный момент устройство выглядит привлекательно по цене и дизайну, но очень страдает от потребления батареи различными программами, в т.ч. использующими WiFi и 3G. Сообщество разработчиков как таковое почти отсутствет, официальное API не выпущено, да еще и портит картину наличие не-рутабельных устройств. С другой стороны, рано или поздно такие устройства будут таки взломаны, а увеличение количества разработчиков позволит оптимизировать п/о и юзабельность.


Ссылки


Прошивка 1.4.0 с разблокированным adbd: http://runserver.net/nook/bravo_update.dat
Прошивка 1.4.1 с разблокированным adbd: http://runserver.net/nook/bravo_update_1.4.1.7z
Домашний экран с отображением установленых программ: http://runserver.net/nook/Home.apk
Браузер с поддержкой скачивания: http://blog.runserver.net/2010/09/nook-2.html
The Daily с поддержкой чтения RSS: http://blog.runserver.net/2010/09/nook-3.html
Патченый services.jar: http://runserver.net/nook/services.7z

Update: Добавил ссылку на новую модификацию Home.apk с папкой Apps вместо Games
Update 2: Добавил ссылку на прошивку 1.4.1. Подходит для старых устройств.

Дальше..

вторник, 12 октября 2010 г.

Информация о системе в .Net

Этот пост скорее просто памятка .Net программистам о том, как получать некоторые важные свойства системы - версию Runtime, 64 или 32-битная система, сколько используется процессоров и пр. Все эти проверки можно найти в интернете или копанием в классах вроде System.Environment, но лично мне удобно держать все в одном вспомогательном классе.

Класс целиком из ядра RunServer:

/// <summary>
/// System information class
/// </summary>
public static class SystemInfo
{
/// <summary>
/// Is there Mono Runtime available?
/// </summary>
public static readonly bool IsMono =
Type.GetType("Mono.Runtime") != null;

/// <summary>
/// Are we on x86 architecture?
/// </summary>
public static readonly bool IsX86 = IntPtr.Size == 4;

/// <summary>
/// Are we on x64 architecture?
/// </summary>
public static readonly bool IsX64 = IntPtr.Size == 8;

/// <summary>
/// Are we using Server Garbage Collector?
/// </summary>
public static readonly bool IsServerGC = GCSettings.IsServerGC;

/// <summary>
/// Is there console windows attached or we are running in
/// service/GUI app?
/// </summary>
public static readonly bool IsConsole =
Console.OpenStandardOutput() != Stream.Null;

/// <summary>
/// Assembly was compiled in Debug mode?
/// </summary>
public static readonly bool IsDebug =
#if DEBUG
true;
#else
false;
#endif

/// <summary>
/// Runtime version
/// </summary>
public static readonly Version RuntimeVersion =
Environment.Version;

/// <summary>
/// Operating System version
/// </summary>
public static readonly Version OSVersion =
Environment.OSVersion.Version;

/// <summary>
/// CPU count
/// </summary>
public static readonly int ProcessorCount =
Environment.ProcessorCount;

/// <summary>
/// Dumps system information the specified stream.
/// </summary>
/// <param name="stream">Output stream</param>
public static void Dump(StreamWriter stream)
{
stream.WriteLine("Is Mono: {0}", IsMono);
stream.WriteLine("Is x86: {0}", IsX86);
stream.WriteLine("Is x64: {0}", IsX64);
stream.WriteLine("Is ServerGC: {0}", IsServerGC);
stream.WriteLine("Is Console: {0}", IsConsole);
stream.WriteLine("Is Debug: {0}", IsDebug);
stream.WriteLine("Runtime Version: {0}", RuntimeVersion);
stream.WriteLine("OS Version: {0}", OSVersion);
stream.WriteLine("CPU Count: {0}", ProcessorCount);
}
}

Дальше..

пятница, 8 октября 2010 г.

Tips for Geeks. Часть 2

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

В этой статье я рассмотрю довольно распостраненный случай - множественную конкатенацию константных строк в С++.


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

Для примера пусть это будет выглядеть так:
void initString(int i, string & str)
{
str.clear();
str += "SOME_TEST_DATA";
if (i % 2)
str += ",DATA_MOD_02";
if (i % 3)
str += ",DATA_MOD_03";
if (i % 5)
str += ",DATA_MOD_05";
if (i % 7)
str += ",DATA_MOD_07";
if (i % 11)
str += ",DATA_MOD_11";
if (i % 13)
str += ",DATA_MOD_13";
if (i % 15)
str += ",MOD_15_EXTRA_DATA";
if (i % 16)
str += ",MOD_16_EXTRA_DATA";
if (i % 21)
str += ",MOD_21_EXTRA_DATA";
if (i % 24)
str += ",MOD_24_EXTRA_DATA";
if (i % 25)
str += ",MOD_25_EXTRA_DATA";
}

Операцию эту выполним в цикле, увеличивая i от 0 до 1000000:

string paramString;
paramString.reserve(1000);
int result = 0;
for(int i=0; i<1000000;i++)
{
initString(i, paramString);
result += paramString.size();
}
Сюда же добавим измерения скорости выполнения. Сразу предупрежу, что результаты заметно зависят от компилятора, процессора и системы в целом. Интересны они лишь для сравнения разных подходов.
С использованием std::string на Athlon 4200 и MS VC++ 2008 мы получаем ~600мс времени выполнения. Много это или мало? Как по мне, для миллиона итераций этого вполне достаточно. Но серия статей не зря называется Tips for Geeks :)

Что происходит, когда к переменной str добавляется "SOME_TEST_DATA"? Если места в буфере достаточно, то произойдет всего три действия: измерение длины добавляемой строки, копирование данных и смещение индекса в переменной str. Мы не сможем оптимизировать копирование и изменение индекса, но так ли нужно в этом случае измерение длин строк (т.е. перебор всех их символов в поисках '\0')? Ведь длину константной строки компилятор знает еще на этапе компиляции.

Для экспериментов сделаем собственный класс custom_string:

class custom_string
{
char * m_data;
int m_allocated;
int m_size;
public:

void reserve(int size)
{
...
}

custom_string & operator += (const char * str)
{
int size = strlen(str);
reserve(size);
memcpy(m_data + m_size, str, size + 1);
m_size += size;
return *this;
}
};

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

Наш тест с таким классом выполняется за те же самые ~600мс, как и с std::string. Есть как минимум два метода "подстегнуть" его работу.
Первый метод очень прост, но может отказаться работать при каких-либо дополнительных условиях, параметрах компиляции и пр. Он состоит в том, чтобы сделать код оператора более привлекательным для инлайнинга. Сделаем так:

void append(const char * str, int size)
{
reserve(size);
memcpy(m_data + m_size, str, size + 1);
m_size += size;
}

custom_string & operator += (const char * str)
{
append(str, strlen(str));
return *this;
}

Не смотря на то, что визуально код почти не изменился, время выполнения его на моем компьютере теперь составляет ~100мс. Я не смотрел в генерируемый ассемблерный код и не изучал причины, но первое, что приходит в голову - оператор += инлайнится, его вызовы заменяются на вызовы append, и расчет длины строки происходит именно на этапе компиляции. Так это или нет, не суть важно, потому что стабильность такой реализации под вопросом - оптимизация как появилась, так может и пропасть для Unicode строк, при сборке под другую ОС и пр., вне зависимости от бубнов __forceinline и нашего желания.

Более универсальный метод основывается на том, что константная строка в С++ может быть представлена в виде массива символов фиксированной длины. Такая запись вполне валидна:

const char something [] = "something";

Для этого трюка мы используем темплейты:

template<int N>
custom_string & operator += (const char (&str)[N])
{
reserve(N - 1);
memcpy(m_data + m_size, str, N);
m_size += N - 1;
return *this;
}

В переменную N компилятор положит длину массива символов, включая и trailing zero.
Тест с таким методом выполняется на моем компьютере примерно за 140мс, что лежит в пределах статистической погрешности от предыдущего метода, но гарантированно будет работать, т.к. соответствует стандарту C++. Единственный недостаток в том, что для каждой длины строки будет создана новая копия метода конкатенации.

Можно ли таким образом "улучшить" std::string? Мои эксперименты показали, что прирост получается не существенный, порядка 50мс на исходном тесте. Такой трюк лучше использовать в собственных строковых классах, а по-честному лучше не использовать вообще (как и самописные классы для примитивов). Не стоит забывать, что сложение миллионов строк - экстраординарная ситуация, которая если и возникает, то редко бывает настолько критичной по времени. Использование же собственных строк, а тем более методов с необычными конструкциями заметно понижает читабельность кода, а значит и возможность его поддержки как автором, так и сторонними специалистами.


Дальше..

среда, 6 октября 2010 г.

Треугольники и память

В эру гига- и терабайтов как-то стало не принято заботиться о том, сколько памяти потребляют данные в памяти. Работы по оптимизации зачастую намного дороже дополнительной ОЗУ и программисты чувствуют себя вольготно, пока не происходит что-то экстраординарное, вроде достижения лимита памяти на процесс на x86 ОС. В такие моменты мы хватаемся за голову (или профайлер) и смотрим, что же поглотило заветные мегабайты.
Эта история о подобном случае, когда хранение 3D моделей в памяти стало неоправданно дорогим из-за избыточности самого распространенного примитива - треугольника.

Для удобства чтения я буду писать код на C#, хотя все описанное можно повторить и в C++, и в Delphi и пр., за исключением последнего абзаца.

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

struct Triangle
{
public Vector A;
public Vector B;
public Vector C;
public bool TwoSided;

float ND;
float Reci;
Vector Normal;
byte K;
byte U;
byte V;
Vector LowerBound;
Vector UpperBound;
}

Значения K, U, V - номера сторон треугольника, Normal - вектор нормали, LowerBound и UpperBound - границы описанного параллелепипеда, а остальные коэффициенты нужны для просчета коллизий. Vector содержит три переменные типа float, т.е. занимает 12 байт, а вся указанная структура занимает 88 байт*. При наличии 10 миллионов треугольников (а это вполне возможно, если мы храним не одну сцену, а весь игровой мир) они все занимают 880+ мегабайт ОЗУ. Если это слишком много, то самым правильным и простым решением будет переход на 64-битную архитектуру, в которой это значение - лишь капля в море. Но если же нам дорог каждый мегабайт, то можно заняться неблагодарным делом оптимизации :)

Первое, что сразу приходит в голову - использовать внешний массив с вершинами - треугольники в модели почти всегда имеют 2-3 общие вершины с соседями. Мы испольузуем три индекса и одну ссылку на массив вершин. Получится всего 16 байт вместо 36 на вершины, но надо не забывать, что сами вершины от этого не исчезнут и должны хранится в неких внешних массивах. При соотношении вершин и треугольников 1 к 3 выходит, что у нас есть отдельно 40 мегабайт вершин, а треугольники занимают теперь 680 мегабайт.
Затем мы можем убрать вектор нормали и вычислять его при необходимости. Также известно, что значения U и V могут быть вычислены из значения K. Таким образом, структура будет занимать уже 56 байт, значит мы уменьшили потребление с 880 до 600 мегабайт, т.е. примерно на 32%, что уже очень неплохо. В общих случаях на такой структуре можно было бы и остановиться:

struct Triangle
{
public int A;
public int B;
public int C;
public Vector [] VertexBuffer;
public bool TwoSided;

float ND;
float Reci;
byte K;
Vector LowerBound;
Vector UpperBound;
}

Следующие шаги уже довольно нетривиальны. У нас есть Bounding Box треугольника, заданный двумя точками - LowerBound и UpperBound. Координаты этих точек составляются из шести координат вершин (наибольшее и наименьше значение X, Y и Z), потому мы можем сказать, что для описания этого бокса достаточно хранить 6 индексов:

int lbx = MinIndex(A.X, B.X, C.X);
int lby = MinIndex(A.Y, B.Y, C.Y);
int lbz = MinIndex(A.Z, B.Z, C.Z);
int ubx = MaxIndex(A.X, B.X, C.X);
int uby = MaxIndex(A.Y, B.Y, C.Y);
int ubz = MaxIndex(A.Z, B.Z, C.Z);

int MaxIndex(float a, float b, float c)
{
return a > b ? a > c ? 0 : 2 : b > c ? : 1 : 2;
}

int MinIndex(float a, float b, float c)
{
return a < b ? a < c ? 0 : 2 : b < c ? : 1 : 2;
}

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

LowerBoundPack = (byte) ((lbx) | (lby << 2) | (lbz << 4));
UpperBoundPack = (byte) ((ubx) | (uby << 2) | (ubz << 4));

Назад в векторы эта данные превращаются довольно просто:

Vector[] abc = {A, B, C};

byte lbx = (byte) (m_lowerBoundPack & 0x3);
byte lby = (byte) ((m_lowerBoundPack >> 2) & 0x3);
byte lbz = (byte) ((m_lowerBoundPack >> 4) & 0x3);

byte ubx = (byte) (m_upperBoundPack & 0x3);
byte uby = (byte) ((m_upperBoundPack >> 2) & 0x3);
byte ubz = (byte) ((m_upperBoundPack >> 4) & 0x3);

Vector lb = new Vector(abc[lbx].X, abc[lby].Y, abc[lbz].Z);
Vector ub = new Vector(abc[ubx].X, abc[uby].Y, abc[ubz].Z);


Но при этом индексы занимают по 6 бит из 8ми, потому мы можем спокойно записать флаг TwoSided и значение K в неиспользованные биты:

LowerBoundPack |= (byte)(K << 6);
if (TwoSided)
UpperBoundPack |= 0x40;

Таким образом структуру мы сократили до 28 байт:

struct Triangle
{
public int A;
public int B;
public int C;
public Vector [] VertexBuffer;

float ND;
float Reci;
byte LowerBoundPack;
byte UpperBoundPack;
}

В памяти наши треугольники будут занимать 280 мегабайт + 40 мегабайт вершин, т.е. 320 мегабайт, что на 63% меньше, чем изначальный вариант.
На этом можно было бы и остановиться, но есть еще один интересный нюанс. По статистике, модели с количеством вершин более 65536 составляют примерно 2% от общего числа, а около 95% моделей содержит от 256 до 65535 с вершин. Выходит, что использовать 32-битные индексы откровенно расточительно. Также нет особой необходимости хранить ссылку на буфер с вершинами для каждого треугольника - это свойство самой модели и должно храниться в ней.

На помощь придут темплейты в C++ или дженерики в C# **:

struct Triangle<T> where T : struct, IConvertible
{
public T A;
public T B;
public T C;

byte LowerBoundPack;
byte UpperBoundPack;
float ND;
float Reci;
}

Такая структура потребует некоторых нюансов в обработке, а также придется использовать ссылку на VertexBuffer из объекта модели. В случае T = short размер структуры будет 16 байт, а для T = int - 24 байта. Таким образом, в памяти наши треугольники с вершинами займут ~200 мегабайт, что в 4.4 раза меньше, чем в изначальной задаче, т.е. оптимизация составила 77% использования памяти.

Стоило ли это того? На первый взгляд стоило, но код обработки таких треугольников стал выполнятся немного медленее и заметно потерял в читаемости. Вывод прост - надо знать меру во всем, даже в оптимизациях. :)



* Все размеры структур в памяти даны с учетом выравнивания и указанного порядка переменных. К примеру, "ручной" подсчет в первой структуре дает 83 байта, т.е. простая перестановка позволила бы получить размер структуры 84 байта
** Для параметра T нужно требование IConvertible, чтобы можно было привести переменные типа T к int с помощью подобной конструкции:
int a = Convert.ToInt32(A);

Дальше..

четверг, 16 сентября 2010 г.

Модификации программ для Nook. Часть 3

Оригинальный инструмент The Daily от B&N не очень часто используется русскоязычными пользователями, по причине полной бесполензности фидов, которые в нем отображаются. Суть этого проекта - модификация The Daily для чтения любых RSS фидов.
Преймущество такой модификации перед альтернативными читалками (Trook) и web-based аггрегаторами в доступе к нужным фидам буквально в два клика. Программа позволяет указывать любые фиды напрямую в файле конфигурации, без использования преобразующих скриптов как в предыдущих версиях.


Настройка

Для списка фидов используется локальный файл "my documents/feeds.xml". Формат файла совпадает с используемым B&N для фидов:
<response>
  <feeds>
    <feed>
      <name>The-eBook forum</name>
      <url>http://www.the-ebook.org/forum/rss.php?f=44</url>
    </feed>
    <feed>
      <name>NookDevs Twitter Feed</name>       <url>http://twitter.com/statuses/user_timeline/94948125.rss</url>
    </feed>
  </feeds>
</response>

Проблемы и недоработки

  • поддержка ссылок и HTML форматирования очень условна и исправить это малореально

  • все фиды грузятся полностью при запуске программы, потому это занимает некоторое время и трафик

  • фиды вроде bash.org.ru/rss грузятся и форматируются неприлично долго

  • если в момент запуска программы WiFi был выключен, есть вероятность, что фиды так и не загрузятся до ее перезапуска



Ссылки для скачивания:
http://runserver.net/nook/TheDaily.apk
пример конфига feeds.xml:
http://runserver.net/nook/feeds.xml
исходный код на smali:
http://runserver.net/nook/Daily.smali.7z

Установка

Для установки надо записать APK файл в папку /system/app, поверх существующего The Daily:
adb push TheDaily.apk /system/app

Также необходимо положить файл feeds.xml в папку my documents на встроенной карте

Дальше..

среда, 15 сентября 2010 г.

Модификации программ для Nook. Часть 2

Не смотря на свои явные достоинства, браузер от NookDevs не распологает к ежедневному пользованию, а браузер от B&N довольно хорош, но не качает файлы. Я не Android-разработчик, потому с нуля писать браузер просто не взялся бы, как и портировать что-то существующее, вроде Opera Mini for Android. На счастье, декомпилированый код браузера B&N показал наличие некоторых огрызков Download Manager, которые в совокупности с здравым смыслом и неким опытом программирования позволили добавить к нему возможность скачивать файлы.

Возможности

По клику по ссылке с файлом браузер открывает окно Downloads и качает файлы в папку "my downloads" (ее надо создать вручную) на внутренней карте. Это же окно доступно через меню GoTo.

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

Ссылка для скачивания
http://runserver.net/nook/Browser.apk

Исходный код на smali:
http://runserver.net/nook/Browser.smali.7z

Установка

Внимание!
При первой установке необходимо очистить БД браузера, иначе попытка скачивания файлов приведет к крашу. При удалении исчезнет история, букмарки и куки.
Команда для удаления:
adb shell rm /data/data/com.bravo.app.browser/databases/browser


Для установки достаточно записать APK файл в папку /system/app, поверх существующего браузера:
adb push Browser.apk /system/app

Дальше..

вторник, 14 сентября 2010 г.

Модификации программ для Nook. Часть 1

Став обладателем ридера B&N Nook, столкнулся с тем, что программы под него довольно неплохи, но изредка могли бы стать еще лучше с парой минимальных изменений. Сами разработчики часто об этом слышат (топик с пожеланиями на официальном форуме перевалил за 800 постов), но последние 3 месяца не было даже намека на новую прошивку и ожидаемые фиксы.
Самая первая модификация затрагивает приложение Home - домашний экран устройства. К нему нельзя добавлять что-то новое, но мне позарез нужна была возможность запускать менеджер приложений, потому после декомпиляции и рекомпиляции вместо шахмат запускается Nook Application Manager. Из менеджера можно запускать любую другую установленную программу (и те же самые оригинальные шахматы). Также менеджер умеет удалять установленые приложения, что тоже бывает полезно. что в результате и было сделано.


Конечно же, упомянутый менеджер должен быть установлен.Модификация подходит только для рутнутых устройств. Был написаный собственный Application Manager, а затем встроен в Home.apk. Папка Games полностью заменена на новую папку Apps, которая отображает все программы на устройстве. Если иконка программы не подходящего вида и размера, она немного модифицируется для соответствия общему стилю. Все изменения сделаны с помощью декомпилятора и компилятора smali.
Долгое нажатие на иконку позволяет удалить приложение.

Ссылка для скачивания:
http://runserver.net/nook/Home.apk

Код для установки:
adb push Home.apk /system/app/


P.S. Полезность данного хака для многих может быть спорна, но лично я игры на букридере запускаю относительно редко, а вот сторонние программы иногда таки нужны, хоть и не настолько часто, чтобы из-за них ставить полностью другой лаунчер от Nookdevs или Mynook.ru.

Update: статья переделана в связи с написанием новой версии домашнего экрана.

Дальше..

понедельник, 19 июля 2010 г.

Что делать, если не хватает памяти?

Ситуация редкая, но, к сожалению, очень актуальная для тех, кто еще не перешел на x64 архитектуру: имеется x86 программа, требовательная к памяти, установлено достаточно ОЗУ (4-8 Гб), но процесс хоть и должен получать порядка 2 ГБ останавливается на 1.7 Гб и дальше либо активно свопит (мучает GC в случае .Net), либо падает с ошибками OOM.

Конечно, можно потратить сколько-то времени и сделать полноценный порт под x64, но для Windows есть еще один "ход конем", позволяющий выделить программе вплоть до 4Гб памяти на х64 системе и до 3Гб на x86. Это актуально как для .Net, так и программ на C++ и других языках.

Сама операция очень проста - берем утилиту EditBin из комплекта Visual C++ 2005/2008/2010 и выполняем команду
editbin.exe OurExe.exe /LARGEADDRESSAWARE

Наличие изменений можно посмотреть сравнив бинарный файл с оригиналом командой fc /bin.

На x86 системах может получиться, что не будет эффекта, пока не будет прописан ключ /3gb в файле boot.ini:
[operating systems]
multi(0)disk(0)rdisk(0)partition(1)\WINDOWS="Windows Server 2003, Enterprise" /fastdetect /3GB


Никакой особой магии и шаманства в этой операции нет, все это давно описано на microsoft.com

Дальше..

понедельник, 5 июля 2010 г.

Tips for Geeks. Часть 1

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


Итого, первый tip. Перебор массива байт.

На первый взгляд, что может быть проще? К примеру, подсчет суммы всех байт массива на С++:

int summ(char * data, size_t length)
{
int result = 0;
for(size_t i=0;i<length;i++)
result+=data[i];
return result;
}

Нормальному человеку я порекомендую оставить этот код как есть. Он работает очень быстро на современных компьютерах и при этом идеально читабелен.
Если же вспомнить, что мы живем в эпоху 32-битных вычислений, а на пороге уже и 64-битные, то оперировать 8-битными числами получается как-то несерьёзно и расточительно.
Я опущу долгие рассуждения и приведу сразу финальный код:

int summ(char * data, size_t length)
{
int result = 0;
int nlength = length & ~3;

size_t i = 0;
for(; i < nlength; i += 4)
for(size_t j=0; j < 4; j++)
result += data[i + j];

for(; i < length; i++)
result += data[i];

return result;
}

Как видно по коду, операция прохода по массиву выполняется в два больших цикла и когда, к примеру, length = 18, первый цикл будет идти от 0 до 15, а второй - от 16 до 17. Цикл с переменной j будет развернут в присваивания со смещением буквально любым компилятором, потому на нем можно не заострять внимание.
Приведенный код приблизительно в полтора раза быстрее побайтового перебора, но при этом гораздо менее читабелен. Еще лучше будет результат если использовать шаг не 4, а 8 байт, но тут уже прирост не так заметен. Если же стоит задача считать не просто сумму, а выполнять на лету шифрование (XOR с константой или номером элемента и пр.), то производительность уже будет зависеть именно от внутренних операций, а не от организации перебора. При этом, чем сложнее код, тем больше ошибок в нём можно допустить.

Мораль же сей басни такова:
Premature optimization is the root of all evil. (c) Knuth, Donald. 1974

Очень многим людям я бы посоветовал распечатать эту аксиому и повесить на стену в сами видном месте.

Дальше..

вторник, 30 марта 2010 г.

SOS.dll в .Net Framework 4.0

На днях обнаружил, что любимый инструмент отладки в .Net 4.0 несколько изменился. Кто не в курсе, что оно такое - читайте на MSDN.
Самое неприятное изменение оказалось в том, что SOS.dll намертво привязан к версии ядра .Net Framework и нельзя использовать эту библиотеку от 4.0 Beta 2 на версии RC 1, да и вообще смешивать библиотеки разных архитектур.
На помощь пришла видоизмененная команда .loadby:

.loadby sos clr

Такой вызов автоматически загрузит нужную версию SOS.dll соответствующей архитектуры.
Детальнее о новых возможностях можно почитать в блогах коллег из Microsoft, например тут: http://blogs.msdn.com/tess/archive/2010/03/01/new-commands-in-sos-for-net-4-0-part-1.aspx
Дальше..

вторник, 9 февраля 2010 г.

.Net Framework 4.0 beta 2

Небольшой пост про знакомство с новым фреймворком.
Бета 2 оказалась довольно юзабельной, потому RunServer теперь поддерживает и ее. Из явных преимуществ я увидел более корректную работу с ThreadPool - меньше спаунится потоков, меньше переключений; также заметно меньше стали потреблять потоки Server GC. Новые возможности C# 4.0 и в целом CLR 4.0 я не трогал - нам важнее совместимость с .Net Framework 2 и стабильность, чем украшательства кода и сомнительные бонусы вроде Parallels Extensions.
Немного расстроило, что в VS 2008 нельзя выбрать новый Target Framework. Надо пользоваться VS 2010 или собирать проект через MSBuild, в командной строке. Для своих целей я нашел достаточно простое решение этого вопроса - указание версии фреймворка через app.config и сборка с таргетингом обычного 2.0 фреймворка:


<?xml version="1.0"?>
<configuration>
<startup>
<supportedRuntime version="v4.0.21006"/>
<supportedRuntime version="v2.0.50727"/>
</startup>
</configuration>

С таким конфигом .exe файл сначала попробует запуститься с .Net 4.0 Runtime, а если его нет - с 2.0. Файлы получаюся немного больше по размеру, чем при "честной" 4.0 сборке, но в производительности я отличий не заметил.
Дальше..

четверг, 21 января 2010 г.

Input/Output Completion Threads в .Net

Несколько лет назад мои поиски оптимальных методов работы с сетью завершились тем, что был написан собственный Native Windows IOCP модуль на C++. Его мы используем и в RunServer, и в собственных игровых проектах; он достаточно гибкий и быстрый.
Но вот недавно появилась задача сделать для RunServer режим "Pure .Net" - возможность работать без привязки к каким-либо системным функциям, чтобы можно было выполняться и на Mono и на гипотетическом Azure.
Различные части ядра - генератор случайных чисел, собственный Thread Pool на том же IOCP - были переделаны без каких-либо заметных потерь и все это "счастье" включается одним дополнительным ключом при компиляции. С сетевой частью все оказалось заметно сложнее. Были реанимированы старые наработки по .Net Sockets и после некоторый доработки запущены в производство.

Я когда-то хотел написать статью об особенностях .Net Sockets для масштабных серверов, но все откладывал "на потом". Сразу хочу предупредить, что все описанное касается TCP.
Первый и самый важный нюанс этих сокетов в том, что асинхронные вызовы (BeginSend/BeginReceive), не смотря на распространенные заблуждения, не используют IOCP. Вместо этого создается событие (аналог WaitHandle), которое ждет появления данных на сокете и затем вызывает коллбек с помощью ThreadPool. Что интересно, если данные в сокете уже есть, то коллбек вызывается сразу же и в том же потоке, что и BeginReceive, но в документации об этом нет ни слова. Зачастую при тестах в локальной сети именно так и происходит и технически можно никогда и не увидеть спауна потоков ThreadPool, а ведь их по-умолчанию разрешено до тысячи (!) на один процессор:
The thread pool has a default size of 250 worker threads per available processor, and 1000 I/O completion threads

Второй нюанс связан с какой-то внутренней особенностью взаимодействия сокетов и ThreadPool. Он достаточно нетривиален и в предварительных тестах его не увидишь. Обычно код коллбека для BeginReceive выглядит примерно так:

private void OnReceive(IAsyncResult asyncResult)
{
SocketError errorCode;
int size = m_socket.EndReceive(asyncResult, out errorCode);

if (errorCode != SocketError.Success)
{
OnError(new SocketException((int) errorCode));
return;
}

OnData(m_buffer, size);
m_socket.BeginReceive(m_buffer, 0, m_buffer.Length, SocketFlags.None, OnReceive, null);
}
Все логично, все корректно. Но на практике возможны интереснейшие казусы. Пока в буфере есть данные, коллбек будет вызываться в том же потоке, что и BeginReceive. Это может быть поток программы или даже один из I/O Completion Threads, ничего криминального в этом нет. Криминал начинается, если данных в буфере нет и мы уже не в потоке программы, а в каком-то из временных. Событие ожидания привязывается к текущему потоку и не отпускает его назад в пул. Для следующего вызова выделяется новый поток из пула и лишь после EndReceive предыдущий поток уходит в пул. На практике при нескольких сотнях соединений происходит постоянное выделение десятков (а иногда и сотен) потоков с возвращением их назад в пул. При использовании gcServer=false это еще и чревато сборкой мусора прямо в теле временного потока, что в .Net 1.1 и 2.0 (до SP 1) вызывало зависание этого потока на длительное время.
Я нашел лишь один метод бороться с этой напастью: не вызывать BeginReceive во временном потоке. Для каждого соединения держится флаг Receiving если идет прием; отдельный поток регулярно просматривает коллекцию сокетов, вызывает BeginReceive для тех, у кого нет флага. Недостаток этого подхода очевиден - чем больше соединений, тем больше может быть время между EndReceive и следующим BeginReceive. Частично это лечится проверкой значения asyncResult.CompletedSynchronously. Если оно true, то этот вызов был синхронным и можно спокойно вызывать BeginReceive прямо из колбека.

Третий нюанс актуален далеко не всегда и не для всех. Суть его в том, что передавая методам BeginSend/BeginReceive какой-то байтовый буфер мы обрекаем его на тяжкую долю: для вызова системных методов (WSASend/WSARecv на Windows) буферы будут зафиксированы в памяти, чему соответствует термин pinned. Такие объекты выпадают из поля зрения GC на некоторое время, не могут быть перемещены и ведут нас прямым путем к фрагментации памяти. Это актуально как для малых объемов, так и для больших. Наилучшим методом борьбы с этим является пулинг. Об этом же говорит и Maoni Stephens:
if you are using the raw socket I/O you do have control over the buffers so you can have a buffer pool and reuse buffers

К сожалению, пул универсальным быть не может - в один момент времени нам надо 10000 буферов, а в другой - всего 500 и хранить все 10000, выделенные в прошлый раз, нет смысла. Размеры пула, минимальные и максимальные размеры буферов и пр. надо подбирать в зависимости от задач и нагрузки, или реализовывать автоматическую балансировку.
В наших тестовых проектах использование .Net Sockets показывает повышенную нагрузку на GC, которая даже при сбалансированном пуле заметно выше, чем с использованием Native IOCP. При использовании gcServer = true эта нагрузка достаточно незначительна (4-5% при 1000 соединений на нашем тестовом сервере), к тому же она приходится на выделенные потоки и не влияет на общий workflow.

Из плюсов использования .Net Sockets я хотел бы выделить достаточно удобные методы работы с ними и меньшую латентность, чем при вызове C++ методов из внешней DLL.
Для клиентов RunServer начиная с версии 2.2 будет возможность проверить и сравнить эти две технологии без каких-либо серьезных изменений в высокоуровневой части.

Дальше..