Я часто думаю, что мне от этого программирования нужно, и понимаю, что мне очень нравится делать микроскопические проекты, демосцены. Все время вспоминая прошлое и прежние времена, когда я радовался кубу, нарисованному где угодно, хоть на туалетной бумаге, теперь я тоже понимаю, что мне все равно нравится рисовать эти кубы. И даже шары (oh my balls!).
Поскольку вчера я сделал шахматную трехмерную доску, то думаю, что можно в принципе, продолжить делать что-то такое в этом же стиле и куда-то складировать на сайте с исходниками, которые никому абсолютно не нужны.
Все что было в детстве — было лучше всего, потому что там радовался всему, даже stosb радовал так, что я аж подпрыгивал от счастья на месте. Раньше у меня были очень простые радости, не то что сейчас, когда ничего не радует, но ладно, это лирическое отступление от темы.
Из ближайших мыслей о проектах — нарисовать стохастические горные вершины, флаппи бёрд, попробовать вырисовывать окружность по принципу вычисления . Есть такой метод довольно простого поиска quadratного корня, через серию вычитаний -1, -3, -5, -7 и так далее. Я уже ранее рассказывал об этом методе, где 1+3+5+7+9 дает значение квадратов от чисел 1,2,3,4 и т.д. Если же действовать в обратную сторону, то получим корень.
Возьмем число 100, вычислим куадраутный корень через серию вычитаний:

1) 100-1=99,
2) 99-3=96,
3) 96-5=91,
4) 91-7=84
5) 84-9=75,
6) 75-11=64,
7) 64-13=51,
8) 51-15=36,
9) 36-17=19,
10) 19-19=0

Количество вычитаний получилось 10. А значит, квадратный корень из 100 будет 10. На верилоге это бы записано было таким образом:

always @(posedge clock) if (A >= B) begin A <= A - B; B <= B + 2; C <= C + 1; end

Где A — исходное число, B=1 на старте, C=0 на старте, и это результат. Ну и A будет в остатке потом. Короче, через серию вычитаний можно добиться вычисления квадратного корня. Есть только один баг в том, что если исходное число например 65535, то придется 255 раз вычесть прежде чем добьемся ответа от него. Есть и другие методы, например, поиск корня через серию делений, например, или там, по табличке искать сначала, двоичной.
Есть быстрый, шустрый метод быстро найти квадратный корень (приблизительно) через подсчет количества значимых битов, для начала. Например, нам надо вычислить быстренько квадратный корневище через такой подсчет. Возьмем крупное число, 25612461 например, что в шестнадцатеричном виде будет 186D0AD, а в двоичном виде:

0001 1000 0110 1101 0000 1010 1101

Сразу быстро можно посчитать высоту последнего разряда у числа, который содержит единицу. И это бит номер 24, начиная с 0. Если разделить число 24 на 2, то получится 12 битов. Это значит что результат корня гарантированно старше чем 2^12, и не меньше чем 4096 (то есть 4096^2=16'777'216). Результат будет находиться между 4096^2 и 8192^2.
Понятное дело, что это является лишь грубой оценкой корня и что придется еще искать, но подобный подход позволяет снизить количество проб c 24 до 12 при бинарном поиске. И конечно же, чем больше число, тем больше оно и занимает времени на поиск решения.

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

• Буфер вершин (vertex), где хранятся все исходные вершины для рендерера
• Буфер индексов (indicied), там хранится номер вершины
• Текстурный буфер для треугольников

Что будет делать видеоускоритель.

• Просматривается буфер вершин, к каждой вершине применяется матрица камеры, то есть, умножается на эту матрицу (она задана float или half-precision значениями). На самом деле для матрицы камеры вполне достаточно даже и half-precision, я думаю.
• Просматривается буфер индексов, проверяя то, где находится та или иная вершина. Если все вершины находятся впереди проецирующей плоскости, то такой треугольник добавляется в буфер очереди на рисование. Если все вершины вне пределов проецирующей плоскости, то треугольник вообще в очередь не добавляется. В случае частичного попадания за плоскость, треугольник разбивается на 2 части и добавляется в очередь как два треугольника. В очередь добавляются уже готовые вершины, не привязанные к vertex/indicies
• Происходит вычисление параметров треугольников для текстурирования и записывается в отдельный буфер. Тут очень много умножений.
• Для каждой точки вычисляется проекция. Здесь уместно использование конвейерного деления для ускорения.
• Все полученные точки треугольников сортируются пирамидальной сортировкой по возрастанию спроецированного Y. Причем сортируется только самая высокая вершина (которая имеет наименьший Y). Также, сортируются именно индексы новых точек. Это нужно для того, чтобы не перемещать большие объемы данных внутри буфера рендеринга, а только лишь индексы. Каждая вершина имеет индекс принадлежности к определенному треугольнику
• И последний этап, это рендер.

При рендере происходит проверка и вовлечение новых треугольников по мере их добавления. К примеру, если будет отсортированный индекс указывать на вершину A треугольника 4, то номер треугольника добавляется в очередь, причем он добавится в очередь только тогда, когда достигнет того же самого Y, что имеет вершина A. Добавляя эту вершину, потребуется узнать также и все остальные его параметры, такие как высота между вершиной A и C, чтобы знать, когда закончить рисование треугольника и удалить его из очереди.
По мере построчного рисования, будет рисоваться буфер из треугольников, интегрально прибавляя значения, формируя точку на текстуре и точку глубины, записывая эти данные в однострочный буфер глубины. Каждый раз после того, как будет нарисована одна линия, этот буфер очищается для новой линии.
Другими словами, на каждой линии будет отрисовываться несколько текущих рисуемых треугольников за раз. После того, как это будет сделано, из полученного буфера размером в одну строку будут скопированы и вычислены текстуры, итоговый цвет записан в видеобуфер и сам строчный буфер очищен для новой строки.
Вот такая вот сложная система.

Заметил, что в последнее время заинтересовался алгоритмами. Недавно писал статью по ханойским башням, а вчера полностью смог разобраться с алгоритмом пирамидальной сортировки. Как же удивительно то, каким образом у меня все так получается. Четко помню, как в 9-м классе мне пытались объяснить этот алгоритм и то, как его абсолютно не понял. И потом не понял, и спустя 10 лет не понял, и спустя 15 лет не понял, и вот понял только вчера, причем, как же это оказалось просто!
Как же так? Почему то, что ранее не мог разобраться в чем-то десятилетиями, дается так легко сейчас? Что изменилось? Говорят, с возрастом все только хуже становится, но похоже, это не всегда так. Лет 10 назад не мог разобраться ни в чем, а сейчас все даётся пока что довольно легко. Ушел ли у меня страх? Нет, он только добавился и с каждым разом добавляется все больше.
Опишу вкратце, в чем суть алгоритма сортировки пирамидой. Сначала надо построить пирамиду, чтобы самый верхний элемент был самым большим, и два дочерних элементах были либо меньше, либо равны верхнему. И так должно быть для каждого элемента. Для того, чтобы это сделать, первоначально надо привести пирамиду в такой вид. Как это сделать — я тут описывать не буду, но сделать это можно довольно просто.
Так вот, когда наверху самый большой элемент, это и хорошо. То есть, сверху пирамиды всегда будет самый большой элемент, абсолютно всегда, потому что мы это ранее сделали. Теперь же надо убрать этот большой элемент, записать в конец пирамиды снизу, а из конца же пирамиды вытащить другой элемент и поставить в корень. Количество элементов в пирамиде уменьшается на 1. Теперь элемент, который поставили в корень, опускаем вниз так, чтобы он был на своем месте. Это делается за log(n) шагов, то есть, за то количество шагов, какая высота у пирамиды. Если у пирамиды 128 элементов, например, то высота ее 7 слоев. Значит, чтобы привести в порядок пирамиду после перестановки, надо сделать 7 обменов (максимум).
После этого, в корне опять появится самый большой элемент из оставшихся данных. Снова относим в конец (в данном случае на предпоследний элемент бывшей пирамиды), и повторяем до тех пор, пока не остается 1 элемент — это корень. Алгоритм заканчивается.
Ясное дело, что на словах ничего неясно, но я буду статью писать про этот метод сортировки. Однако, это классно, что получилось в этом разобраться. Вообще-то, хотел этот метод сортировки применить для задачи трехмерного рендеринга на ПЛИС, но так не уверен, что дойду вообще до этой задачи. Она не такая сложная, просто надо очень много делать и мне ужасно лень.

Оказалось, это не так и сложно, если тщательно все продумать. Код получился очень даже небольшим, где-то на 200 строк всего лишь. Для сжатия я использовал код Хаффмана, который уже давно изучал, но никак не мог реализовать его в виде программы на C/C++ и вот у меня получилось это сделать. Вчера сделал на Си, а сегодня переписал на использование классов, поскольку это удобнее получается намного. Код, правда, еще не доделан и ему достаточно далеко до завершения. Нужно придумать как хранить файл.
Например, я могу формировать файл .wah, в котором будут следующие поля:

• Частота дискретизации (1 байт)
• Стартовый байт
• 512 байт для воссоздания дерева Хаффмана
• Весь оставшийся код

Хранить данные для дерева довольно просто. Первые 256 байт всегда будут указывать на родительский элемент 256 + n, где n=0..254 (родительских элементов может быть максимум 255), а код номер 255 будет означать, что этот символ пустой. Причем, кстати интересно, если указывать родителя, то в заданной таблице всегда будет левая и правая часть (0 и 1). Слева будет потомок 0, справа — потомок 1. Это очень важно, поскольку именно так кодируется дерево.
Для остальных 256 все точно так же, в том числе порядок потомков. Если к примеру, из диапазона первых 256 указывает на родителя 5, и из диапазона 512 тоже на родителя 5, то первый будет потомок ветки 0, второй — ветки 1. Таким образом, можно закодировать все дерево через 512 байт. Но это, конечно же, надо проверить. Надеюсь, у меня получится.
Да, еще вчера все же заказал книгу по FoxPro 2.0 с Озона. Хорошо бы, если она у меня была. Может, я даже ее частично прочту.

Уже не помню, когда и как я впервые услышал про этот алгоритм, но как и обычно, это было очень давно и выдумка. Обычно я сначала узнаю о чем-то, а через год, два или даже десять лет изучаю этот вопрос и реализовываю. Так же произошло и с кодом Хаффмана. Как и обычно, я сразу не смог его понять, мне показался он чересчур сложным и потому просто не стал изучать, да и всё. Впервые серьезно пытался его разобрать я после того, как однажды мы как-то зашли в магазин и купили там книгу по распродаже, она называлась что-то вроде "алгоритмы изображений", я уже реально не помню как, а книгу я эту читал очень поверхностно.
В этой книге тоже был описан алгоритм кода Хаффмана, но я его опять не понял, хоть и пытался. Но не понял. Там в этой книге, помимо Хаффмана, еще были и gif, и png, и jpg — все основные картинки в интернете. Не спорю, книга хорошая, но я не умею читать книги, просто не могу, не получается. Мне подходят различные короткие статьи с интернета, а не книги. С последних толка никакого.
Окончательно я с этим алгоритмом смог разобраться только в прошлом году. При помощи страшных мучений примитивного мозга, преодоление препятствия было выполнено, и у меня получилось даже написать алгоритм как на PHP (Pre Historic Programming, в переводе как До Историческое Программирование - ДИП), так и на Си, который является языком, на котором программируют сейчас абсолютно все и который является языком для мажоров. Ладно, я опять отступил от темы, как обычно.
Этот алгоритм Хаффмана интересен тем, что он работает только для алфавита из фиксированного количества символов, при этом необходимо, чтобы частота встречи каждого символа очень сильно различалась, чтобы каким-то образом попытаться сжать эти данные. Эффект кода Хаффмана заключается в том, чтобы сжимать более часто встречающиеся символы более короткими кодами и это факт. Этот алгоритм очень распространен, используясь везде где можно и где не можно. Да, кстати, насчет этого...
Мне пришла мысль, а что если кодировать музыку через Хаффмана? Степень сжатия, конечно, не всегда может быть, но вот как кодировать музыку? Самая первая мысль, которая у меня была, это взять все семплы, подсчитать их частотность и закодировать. Но эта мысль оказалась ошибочной, сжатия почти не было, какие-то жалкие проценты. И тут я подумал о втором варианте — кодировать не сами семплы, а разницу между ними. Вот здесь все получилось гораздо успешнее!
Для этого я написал алгоритм по-быстрому, чтобы проверить догадку. Действительно, сжатие удается до 44% примерно для аудиотрека, что чуть больше чем в 2 раза. Для очень хороших случаев сжимать получается и до 15%, но это в хороших случаях, а вообще, кодом Хаффмана более чем в 8 раз не получится сжать, потому что минимальный код — это 1 бит, который бы кодировал 8 бит.
Я не придумывал какой-то собственный формат, но мне было реально интересно, что получится и получится ли сжатие, и у меня получилось. На данный момент у меня нет реализации формата этого файла для сжатия, так что думаю, что надо будет над этим подумать, и попробовать сделать. Как обычно, через пару месяцев или через пару лет, по традиции. Кто здесь главный слоупок? Я, конечно!

Как же давно я хотел написать эту статью по этим кодам, и вот день этот настал и я смог затащить эту изи-катку, как выражаются CS:GO-еры. Интерес к этому коду у меня возник еще тогда, когда я обнаружил, что SDRAM-память для Марсохода2 у меня жестко сбоит и совершает непоправимые ошибки. Видимо, память битая оказалась, что очень плохо. Тогда я стал искать, как это исправить и наткнулся на статью о том, что существует волшебный метод, как исправить единичные ошибки в сообщении. И это оказался код Хэмминга.
Сначала я пытался его понять, но у меня не получилось разобраться в самой сути. Я читал в разных источниках, но не находил простого объяснения, как именно это дело работает. И вот вчера как говорится, психанул и начал искать. Вначале сам прикинул, как это может работать, а потом прочел прекрасную статью от хабраюзера и на меня прямо снизошло Знание!

Сообщение	r0	r1	0	r2	1	2	3	r3	4	5	6	7
Бит №	1	2	3	4	5	6	7	8	9	10	11	12
Бит #0	x		x		x		x		x		x
Бит #1		x	x			x	x			x	x
Бит #2				x	x	x	x					x
Бит #3								x	x	x	x	x

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