Sunday, September 12, 2010

Ubuntu beta: Hybrid graphics

В бета версии(как у знал в понедельник это бета версия) ubuntu в настройках ядра включили поддержку vgaswitcheroo. Переключать можно только магической посылкой определенной комбинации символов в определенный файл:-) Или проще говоря поддержки на уровне пользовательских программ нет, переключать можно только применяя команды описанные ранее.
Толку для игр от этого мало - так как в бета релизе у меня не работает нормально opengl - картинка представляет собой появляющиеся и исчезающие полигоны, играть нормально нельзя.
Зато проверил hdmi(фильмы на большом экране смотреть:-)) он нормально работает экранами через пользовательские программы можно управлять, звук есть. Ранее проверить нельзя было, так как разьем выведен с 3650 и управлять им с 3200 нельзя. Зато глюков с экранами нет - windows иногда забывала где основной и выводила на hdmi приглашения входа.
P.S.: Плюс очень большое количество fps в glxgears: 3200 - 270fps, 3650 - 320fps. Но я думаю эту мелкую неудобность к релизу исправят.

Monday, September 6, 2010

Асинхронно выводить на экран?

Или маленькая мысль о том:
так ли X-протокол безнадежно устарел.

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

В общем идея такая: в отдельном потоке держать обработку списка задач которые синхронно отсылаются на сервер (возможно похоже на случай с Beos, где в app-server запущен еще один дополнительный поток на каждое окно, если верить некоторым публикациям), если потребность в них отпала - пользователь или кто то еще изменил существенно прорисовку зачем продолжать? Так мы можем определить, что за секунду мы прорисовываем 1000 примитивов и постепенно прорисовывать их пока не закончиться временной лимит, или кто-то не отменит прорисовку. В результате того как сейчас работает X протокол мы можем, если пользователь был не очень активен последнее время - с устройств ввода не было событий мы можем спокойно поставить проверку на ввод после n-го элемента(или по времени смотря что раньше произойдет), что выведет проверку на состояние каждые 1 секунду, и когда появляется активность ставить проверку на десятые доли секунды. Думаю это существенно снизит нагрузку на процессор.

Для OpenGL- есть примерно подобная идея - создавать буфер для списка отображаемых объектов (буфер глубины), но не для конечных точек, а для больших объектов. И отбрасывать сразу целыми объектами, и если мы не попадаем в какой-то лимит отображения за время, например кадров секунду, отбрасывать все мелкие объекты(или те которые большие, но далеко) и следующий кадр рисовать уже без них, так как в основном все кадры подобны это должно дать несколько дерганое время прорисовки кадров, которое стремится оптимизироваться под соотношение размер элемента/время кадра. Правда я не уверен, есть ли сейчас отбрасывание объектов сразу при начале заполнения очереди, но отбрасывания по размерам объектов (не примитивов) я не слышал, и в классическом рисунке графического конвейера его не видно.

Sunday, September 5, 2010

Псевдослучайное сжатие

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

Это было давно, как теперь кажется, я учился в университете и полдня мне рассказывали интересные штуки(кроме случаев когда рассказывали не очень).

И на предмете защита информации, или как-то подобно называвшемся, очень часто предметы имели длинные названия, которые все сокращали до очень кратких фраз, была у нас тема псевдослучайные последовательности на основе xor и регистров сдвига. Это очень простые по логике устройства умевшие генерировать n-1 чисел, где n это 2 в степени разрядности регистра сдвига. Почему на одно число меньше, если это очень хорошее число установить в регистре сдвига, то он будет всегда выдавать только его. Все остальные числа спокойно переходили одно в другое по случайному закону, но всегда по одной последовательности. Ну зато они и псевдослучайная последовательность. Разнообразие этих генераторов немного все таки ограничено, так некоторые варианты, как я помню можно упростить до более простых.

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

Он заключался как я помню в том чтобы выписать эту всю последовательность в виде треугольника, так как в качестве результата всегда выдавалось полное содержимое регистра сдвига без изменений. То-есть в первой строке первый известное состояние когда известны все биты в регистре, в следующем со сдвигом на один разряд, неизвестен 1 бит. И так до конечного состояния. Теперь предполагая о предположительной длине этого регистра сдвига, в моем случае это было просто, я знал что длина исходных данных равна половине полной последовательности и мог четко предположить, что регистр сдвига будет определенной длины. Хотя это в общем-то особого значения так как этот алгоритм можно использовать и для неизвестной длины цепочки, только корректируя результирующую формулу. В этом случае - нужно выполнить полный перебор всех возможных значений формулы от минимального до максимально возможной разрядности. Что хорошо для медленной скорости передачи исходной последовательности, но для случае если скорость передачи сравнима со скоростью пересчета то смысла в этом алгоритме нет, он не дает той-же скорости как исходный классический метод с мнимыми числами.

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


Как я выше указал мы берем от совсем минимальной длины регистра сдвига до максимально возможной для данной последовательности - мы где-то можем примерно проверить разрядность до длины полученной последовательности-2. Причина в том что на полной последовательности мы ничего проверить не можем, на -1 мы можем хоть уже делать предположения, о том какие настройки возможны, на -2 можем начать отбрасывать точно не подходящие и прогнозировать множество возможных вариантов. Но так как мы начинаем с минимального - мы делаем предположение основываясь множестве уравнений полученных вычитанием верхней строки из строки расположенной на 1 строку ниже. Чем длиннее предполагаемая разрядность, тем меньше уравнений и больше множество вариантов. И начиная с минимальной разрядности мы отбрасываем варианты.

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

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

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