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

Задача сравнения двух директорий возникает более-менее часто и стандартные 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

Дальше..

Рутинг 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

Дальше..

Не канонический взгляд на 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. Подходит для старых устройств.

Дальше..

Информация о системе в .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);
    }
}

Дальше..

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мс на исходном тесте. Такой трюк лучше использовать в собственных строковых классах, а по-честному лучше не использовать вообще (как и самописные классы для примитивов). Не стоит забывать, что сложение миллионов строк - экстраординарная ситуация, которая если и возникает, то редко бывает настолько критичной по времени. Использование же собственных строк, а тем более методов с необычными конструкциями заметно понижает читабельность кода, а значит и возможность его поддержки как автором, так и сторонними специалистами.

Дальше..

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

В эру гига- и терабайтов как-то стало не принято заботиться о том, сколько памяти потребляют данные в памяти. Работы по оптимизации зачастую намного дороже дополнительной ОЗУ и программисты чувствуют себя вольготно, пока не происходит что-то экстраординарное, вроде достижения лимита памяти на процесс на 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);

Дальше..