nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Супрематический алгоритм обнаружения на ассемблере (часть 2)

Продолжаем ковырять этот код. Реально, он самый тяжёлый во всём этом проекте - аффинный алгоритм тоже не сахар, но там всё разбито на короткие шаги, каждый из которых можно писать и отлаживать по отдельности: нахождение самой отдалённой точки, сортировка остальных "против часовой стрелки", получение матрицы аффинного преобразования, выделение крена, выделение масштаба, нахождение вектора параллельного переноса. Да и ветвлений там практически не было. Были вложенные циклы, до трёх штук, что во время перемножения матриц немудрено, но это гораздо проще!

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

Для начала вспомним оставшейся код. Когда взгляд не замылился ещё, видишь, что этот код далеко не оптимален!

Вот, к примеру, пресловутый @@MidCycle, где мы обработали отрезок, расположенный между двумя пятнами, а теперь смотрим, не является ли правое пятно "фиктивным", означающим завершение строки:

;теперь надо посмотреть - а есть ли точка? Или мы уже прошли последний отрезок между точками?
;но у нас в конце списка правая фиктивная точка - её надо игнорировать!			
@@MidCycle:	Y	X
		X	[X+k]								
		ZAcc	RoundZero
		SUB	[X+k]
		JGE	@@FinalRange	;наткнулись на NULL, значит, все точки обработали...


Можно укоротить на одну строку!


Вот взял и забыл о такой замечательной возможности, проверять конкретно на число "-32768", оно же 0x8000, с помощью команды ABS (взять абсолютное значение, то есть модуль числа). Из всех 16-битных значений в дополнительном коде, только у -32768 нет "пары", и происходит переполнение. И затем с помощью JO / JNO можно произвести ветвление.

Профит, что не нужно аккумулятор предварительно инициализировать, как в случае команды SUB. Дополнительный профит - теоретически у меня здесь может быть задействовано 65635 ячеек памяти, т.е "зарезервированной" под NULL окажется лишь одна, а не сразу половина адресного пространства, как было в случае SUB (проверки на знак числа).

Правда, даже зная это, укоротить этот код не так-то просто! Если мы просто напишем:
@@MidCycle:	Y	X
		X	[X+k]
		ABS	[X+k]
		JO	@@FinalRange


то нарвёмся на RAW Hazard (Read After Write): запись нового значения в регистр X на 2-й строке совпадёт по времени с чтением по адресу [X+k] на 3-й строке, что будет нарушением логики работы, и компилятор вставит посерединке NOP 0, съедая наш выигрыш :)

По-моему, единственный способ таков:
@@MidCycle:	%CheckHazards OFF
		X	[X+k]
		Y	X
		%CheckHazards ON
		ABS	[X+k]
		JO	@@FinalRange


Нужно запустить обновление регистра X тактом раньше, чтобы к моменту выборки [X+k] для команды ABS там уже было нужное нам значение, поэтому ставим его даже раньше "Y X". И мы знаем, что выборка X для этой команды произойдёт на том же такте, к концу которого "защёлкнется" новое значение X, поэтому значение мы возьмём старое, как и надо. Остаётся лишь указать компилятору, что это НЕ БАГ, А ФИЧА, чтобы он не вставил туда NOP.

может, потому и забраковал ABS изначально, что казалось, что он выигрыша не даст?

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

На этот момент мы знаем значения регистров X (текущее пятно в списке),Y (предыдущее пятно в списке), SP (указатель стека), i=0, j=1, k=0

Поехали дальше:
;запрашиваем отрезок, где ожидаем точку. Первой придёт яркость, как всегда
		[SP+2j+1]	GPUL		;яркость
		Acc		GPUL
		SUB		[X+4j+k]						
		[SP+1]		GPUH		;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 
		[SP++]		@@ActPointsStart	;нам по-любому придётся вернуться именно сюда!
		JL		AcqAndUpdate	;отсюда "выпрыгнем" сразу на метку @@ActPointsStart						


Напомним, как у нас хранятся данные. Каждое пятно из списка состоит из 5 слов:
[X] - указатель на следующее пятно (правее текущего),
[X+1] - диаметр пятна,
[X+2] - X-координата центра,
[X+3] - Y-координата центра,
[X+4] - максимальная яркость пятна.

На стеке мы храним локальные переменные:
[SP] - рискованно, при вызове процедуры затирается,
[SP+1] - X-координата обнаруженной точки,
[SP+2] - текущая строка (она же, по совместительству Y-координата обнаруженной точки :)),
[SP+3] - яркость обнаруженной точки.

Итак, в [SP+3], а заодно в аккумулятор мы помещаем максимальную яркость на отрезке. Вычитаем яркость пятна (лежит в [X+4]), помещаем в [SP+1] X-координату обнаруженной точки (потом начнутся ветвления, не до того будет!), и затем делаем ФИНТ УШАМИ, который, возможно, придётся скорректировать. А именно, кладём "адрес возврата" в стек, чтобы потом легко и непринуждённо идти в процедуру AcqAndUpdate либо AcqNoUpdate ПО КОМАНДАМ УСЛОВНОГО ПЕРЕХОДА, зная, что возвратимся оттуда ровно туда, куда хотели.

В данном случае, если обнаруженная нами точка оказалась ярче, мы переходим в AcqAndUpdate, где в [X+2], [X+3], [X+4] (X,Y-координаты и яркость пятна) заносятся [SP+1], [SP+2] и [SP+3] соответственно (только после занесения в стек адреса возврата это выходит [SP], [SP+1] и [SP+2]). И затем сразу же выдаём задания на обработку.

Если у нас есть команда AUP, то всё верно, никаких проблем. Если её нет, то обновить значения надо сразу, а вот выдавать задания торопиться не надо! Вместо этого нужно записать: "за нами должок!"

Посмотрим, что происходит, если новая точка вовсе не ярче предыдущей:
	;ветвь исполнения, если старая точка оказывалась ярче.
	;Нужно сообразить: не пора ли ей на покой, то бишь в список AllPoints?
	;в кои-то веки работаем с Y-координатой!
	Acc	[X+2j+1]	;координата точки (из списка)
	DIV2A	[X+1]		;прибавить половинку её диаметра
	SUB	[SP+1]		;вычесть текущий номер строки
	JGE	AcqNoUpd	;здесь ОБЯЗАН быть именно JGE, т.к флаг знака является одним из "аргументов" для AcqQueue


Проверяем, что Y + D/2 - y >= 0, где Y - координата центра пятна, D-его диаметр, y - текущий номер строки. Иными словами, этот отрезок всё ещё относится к нашему пятну. Тогда мы прыгаем на AcqNoUpd - параметры пятна не обновляем (ничего примечательного на текущей строки мы не обнаружили!), но задания на обработку отправляем.

Если у нас есть команда AUP, то всё верно. Если её нет, то выдавать задания на обработку не надо, только записать "за нами должок!"

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

	;пора эту точку перетаскивать в другой список... 
	X	AllPoints
	CALL	ListOp
	X	Y		;теперь [X] ссылается уже не на обработанную и удалённую точку, а на следующую, так что всё верно
	JMP	[--SP]		;ура...					


Тут в любом случае нужно добавить ещё одно условие, проверить, что Y + D/2 - y + D1 >= 0 и в то же время яркость обнаруженной точки выше пороговой.
В таком случае нужно будет "уширить пятно вниз": чуть сдвинуть координату его центра, а также нарастить диаметр. Именно таким образом пятно способно "отцентрироваться" в ситуации, когда мы видим равномерную "блямбу". Изначально я больше полагался на такие пятна, где яркость растёт по мере приближения к центру, и такое действительно имеет место быть на больших дальностях, порядка 300 метров, но здесь, вблизи, оно так не работает...

И кроме обновления параметров пятна (Y-координаты и диаметра), при наличии команды AUP нужно будет выдать задания на обработку, в противном случае - записать "за нами должок!".

И наконец, если ни одно из условий не выполнено, то мы действительно перетаскиваем точку в другой список, и записку "за нами должок" УДАЛЯЕМ!

Остаётся самая простая часть кода, начинающаяся с метки @@FinalRange:

@@FinalRange:	ACQ	WholeRow
		ACQ	HSync
		Acc	[SP+2j]
		SUB	ImgHeight
		ADD	ImgHeightP1
		JL	@@newRow
		;усё, отстрелялись...


Выдать два последних задания ("до конца строки" и "дождаться строчного синхроимпульса"), проверить, не последняя ли у нас строка, прибавить единичку, и если строка ещё не последняя - вернуться в начало цикла по строкам.

Тут тоже есть, что оптимизировать: можно всё-таки нумеровать строки снизу вверх, тогда хватит обычного вычитания единички и проверки на ноль, вместо нашей переусложнённой методы "вычесть H, прибавить (H+1)". Это тоже своего рода Legacy, когда мы думали рассмотреть эдак на сотню строк больше, чтобы там "естественным путём" все элементы из списка ActivePoints переползли в список AllPoints. Сейчас у меня написан код, чтобы сделать это "в лоб":

		;надо ещё все оставшиеся в ActivePoints точки "перецепить" в AllPoints
		Y	ActivePoints	;это заведомо фиктивная, и указывает либо на другую фиктивную, то ли на реальную
		X	AllPoints
		Y	[Y+k]			;это уже может быть реальная точка, а может быть правой фиктивной
@@Transfer:	ZAcc	RoundZero
		SUB	[Y+k]			;если [Y+k]=NULL, значит пора закругляться
		[SP++]	@@Transfer
		JL	ListOp
		NOP	[--SP]		;раз не было вызова - возвращаем стек в исходное состояние


На всё про всё 8 строк, а скорее всего хватило бы и 6 (не выпендриваться со стеком, а вместо этого выпендриться с ABS). Пущай пока будет. Станет совсем невмоготу - выкинем!

Осталось понять, как именно всё это дополнить, в первую очередь, если мы не хотим вводить команду AUP.
Приходим к выводу, что процедура AcqAndUpdate по сути должна распасться на две части! Отдельно Update: обновление параметров точки, когда новым центром становится только что обнаруженная точка. Делается это дважды: либо когда действительно мы обнаружили НОВОЕ пятно, либо когда ПОД существующим обнаружили более яркую точку. Вторую ситуацию на самом деле можно "зарезать"! (на модели это уже проверил, работает как не в чём не бывало). Так что обновление выведем из-под процедуры, это просто будет коротенький код при добавлении нового пятна.

И отдельно Acq, т.е выдача заданий на "захват", фактически внутри процедуры TaskPending.

Что представляет запись "за нами должок" - пусть это будет регистр C, в котором мы раньше хранили значение D1, загруженное из памяти, пока не решили, что это вообще-то будет константа. Имеет смысл использовать всё то же "волшебное значение" -32768, или 0x8000, которое легко будет проверить с помощью "ABS C" и затем ветвление по JO / JNO.

И надо ещё определиться с "конвенцией вызова", проще говоря, куда мы будем запихивать адрес возврата. Моя вчерашняя бредовая идея с регистром Y была вызвана тем, что [SP] именно в этот момент мы использовали, чтобы хранить расстояние между обнаруженной точкой и одним из пятен. Правда, вчера же оказалось, что оно нам не шибко нужно, так что [SP] освободилось, можно вернуться к классическому вызову процедур. Или использовать [SP], но без инкремента, тоже вариант.


Продолжение следует...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Доработка "студийного освещения" и новое видео от брата

    Когда только началось веселье с самоизоляцией, практически собрал "студийное освещение" брату для записи на ютуб ( раз, два, три) Даже одну…

  • Брат выложил новое видео :)

    После 3-летнего перерыва! Перерыв был вызван институтом и очень затяжным ремонтом - решили звукоизолировать комнату, чтобы она стала ближе к…

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

    Еще 14 сборников готовы: По просьбе модератора с рутрекера, я начал сканирование со сборников для детей. Вообще, в…

  • "Люди идут по свету"

    Продолжим с песенниками, в этот раз под гитару. Содержание: Вместо предисловия. А. Городницкий Первое отделение. Река с простым названьем…

  • Разноцветные песенки

    Начнем с чего попроще: Прекрасное Далеко, затем Пластилиновая ворона - уже ради них стоит скачать, фортепианная партия довольно простая, когда-то…

  • Сканируем ноты

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments