nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

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

Пора подправить алгоритм обнаружения, написанный на ассемблере, в соответствии с новым алгоритмом, который даёт корректные результаты.

И по ходу дела надо будет сообразить, нужна ли нам новая команда видеообработчику AUP (Acquire UPdate), или достаточно будет переписать программу. Начнём с самого начала файла ProcessFrame.asm:

ProcessFrame proc			
			j	1		;отныне и во веки веков!	
						;ждём кадрового синхроимпульса
			ACQ	VSync		;"застревает" до тех пор, пока кадровый импульс не придёт
						;пропускаем "пустые строки" вверху изображения (нужно только для аналоговой камеры, в цифровой такой фигни нет вроде бы...)
			k	TopRows		;TopRows должны быть определены в основном файле
			Z	D1												
	@@topRows:	ACQ	HSync
			kLOOP	@@topRows
						;теперь k=0, пусть так и остаётся, наши [X+k], [Y+k], [Z+k] будут означать [X],[Y],[Z], очень надо для списков
						
				;теперь начинаются информативные строки изображения, сейчас их 720, позже может стать 1024. 
			C	[Z+k]		;ожидаемый диаметр точки, всё-таки штука весьма нужная, лучше держать локальной перем.											
			[SP+2j]	0		;в [SP+2] храним номер строки. 
						
			JMP	@@FinalRange	;чтобы СНАЧАЛА отправить запрос, а потом уже смотреть результат, так почему-то удобнее					
						;можем заменить на JNO, переполнения здесь случаться не должно


Как ни странно, здесь нас ждёт УПРОЩЕНИЕ - выкидываем аж две строки!


А именно, мы мучительно подгружали из памяти переменную D1 в регистр C (сначала присваивали Z = D1, т.е адрес переменной, а потом по [Z+k] загружали значение), предполагая, что этот D1 (номинальный диаметр пятен) будет определяться исходя из выставленной экспозиции. Но по счастью, теперь нас устраивает D1=3, а реальные диаметры алгоритм найдёт сам! А раз так, можно вместо переменной взять просто константу, т.е

D1   EQU 3


и где нужно, она будет браться как "непосредственное значение" (Immediate value). Комментарий про замену JMP на JNO - из тех времён, когда у нас были абсолютные адреса для JMP и относительные для условных переходов, и относительные были предпочтительнее. Сейчас мы повсюду поставили абсолютные адреса, не уверен, что это правильно, как-то резво начали "непосредственные значения" наполняться, а их у меня всего 128. А пока этот комментарий можно и выкинуть, система контроля версий всё помнит.
Получается так:

ProcessFrame proc			
			j	1		;отныне и во веки веков!	
						;ждём кадрового синхроимпульса
			ACQ	VSync		;"застревает" до тех пор, пока кадровый импульс не придёт
						;пропускаем "пустые строки" вверху изображения (нужно только для аналоговой камеры, в цифровой такой фигни нет вроде бы...)
			k	TopRows		;TopRows должны быть определены в основном файле												
	@@topRows:	ACQ	HSync
			kLOOP	@@topRows
						;теперь k=0, пусть так и остаётся, наши [X+k], [Y+k], [Z+k] будут означать [X],[Y],[Z], очень надо для списков
						
						;теперь начинаются информативные строки изображения, сейчас их 720, позже может стать 1024. 
			[SP+2j]	0		;в [SP+2] храним номер строки.
						
			JMP	@@FinalRange	;чтобы СНАЧАЛА отправить запрос, а потом уже смотреть результат, так почему-то удобнее					


Пока всё хорошо. Поехали дальше:

						;НАЧАЛО ЦИКЛА ПО СТРОКАМ
	@@newRow:		[SP+2j]		Acc
				X		ActivePoints	;начинаем цикл по всем активным точкам
			
			;даже если список пуст, первую половину цикла мы пройдём, она касается отрезка, предшествующего точке из списка
	@@ActPointsStart:	[SP+2j+1]	GPUL			;яркость самой яркой точки на отрезке
				[SP+1]		GPUH			;соотв. координата
				Acc		Threshold		;поставили задом наперёд, чтобы избежать Hazard'а	
				SUB		[SP+2j+1]		;вычитаем порог, положит. значение свидетельствует о новом найденном "пятне"						
				JL		@@MidCycle		;пятна нет, не торопимся заказывать отрезок


Итак, идёт очередная строка, мы заканчиваем возню с номером строки, мы обновили её значение в аккумуляторе Acc, а теперь помещаем на должное место. Поместили именно здесь, чтобы избежать очередного Hazard'а, точнее там даже блокировка есть в аккумуляторе, просто мы торжественно сэкономили 1 такт. Ладно, пущай, работает-не лезь!

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

На самом деле, если яркой точки мы не нашли, нужно проверить - "есть ли за нами должок по отправленным заданиям", и если да - отправить их. Но если точка нашлась, то пороть горячку нельзя, потому как это задание мы ещё, возможно, скорректируем! Если всё-таки ввести команду AUP, то менять ничего не надо. В противном случае - прыгать надо не сразу на @@MidCycle, а на отдельный закуток @@TaskPending, которого у нас ещё нет, но сейчас сообразим. Тогда заменяем нижнюю строку на две:

   Y    @@MidCycle
   JL   @@TaskPending

То есть, @@TaskPending будет процедурой в своём роде, но с чуть другой "конвенцией" вызова: вместо стека мы будем использовать для адреса возврата регистр Y. Так надо, поскольку в 3-4 разных местах нам по выходу из TaskPending надо будет попасть аккурат в @@MidCycle, и только в одном месте - по другому адресу, поэтому удобнее будет там "переписать" Y. А если использовать [SP++], это неудобно, у нас доступа к [SP-1] нету! Кроме того, именно [SP] будет использован для хранения разности между обнаруженной точкой и одним из пятен, и затирать его не хочется по чём зря...

На следующий участок кода мы попадаем, если всё-таки нашли достаточно яркую точку, поэтому не выпрыгнули по JL:

		;пятно есть. Надо проверить: не сливается ли оно с пятном слева или с пятном справа
		;X сейчас указывает на точку, расположенную слева (возможно, фиктивную, нам не важно)
		;коорд. текущей точки лежит в Acc, её яркость в C
		Z	X		;Чтобы в Merge всегда использовать Z, независимо от того, левая или правая точка оказались
		i	1
@@checkCycle:	Acc	[SP+1]
		SUB	[Z+2j+k]
		ABS	Acc
		[SP]	Acc		;модуль разности - это и будет новый "диаметр" точки, если сработает слияние
		DIV2S	C		;не будем мудрить пока что, всё "в лоб"
		DIV2S	[Z+1]						
		JL	@@DoMerge
		Z	[X+k]
		iLOOP	@@checkCycle
		;если попали сюда, значит слияния не было, и точку всё-таки надо добавить!


Как явствует из комментариев, мы проверяем, не "сливается" ли только что обнаруженная точка с пятном слева или справа от себя. Худо-бедно мы умудрились ДВЕ этих проверки упихать в цикл, ради экономии аж 2 строк!
Хотя, чуточку больше: идея была, что Z будет указывать на пятно, к которому надо "прибавить" только что обнаруженную точку, и коду для слияния, лежащему на @@DoMerge, и не нужно будет знать, слева это или справа.

Сейчас всё немножко сложнее: если мы обнаруживаем близость к пятну слева от себя, то хотим ещё проверить - не пора ли произвести слияние с пятном справа? Если пора - обновляем параметры пятна, удаляем одно "лишнее" пятно, и если у нас есть команда AUP - применяем её, чтобы подправить, до какой координаты обрабатывать следующий отрезок. Если её нет, мы просто пока не выдаём задание - чтобы не сбиться с получением уже обработанных отрезков (а они были и на только что удалённое нами пятно), мы должны "сделать вид", что пятно ещё не удалили, и вот в этот момент новое задание, с правильными координатами, и будет отправлено!

Если же слияние с пятном справа производить не надо (только точку добавить) - ничего страшного, всё так же обновляем параметры пятна, и выдаём задание на обработку следующей строки (либо с помощью AUP, корректируя ранее выданное задание, либо отправляя его прямо сейчас, точно зная, что "надо").

И наконец, если только что обнаруженная точка подошла предельно близко к пятну СПРАВА от себя, мы обновляем параметры этого пятна, и не забываем выдать задание на обработку пятна СЛЕВА (если у нас нет AUP, если есть то всё хорошо, уже раньше выдали), так как пока мы возились именно с ним.

Если же новая точка оказывается "сама по себе, своя собственная", мы, прежде чем добавить её и дать задание на её обработку на следующую строку, если команды AUP нет, должны выдать задание на предыдущее пятно! Именно в этой ситуации, по добавлению задания на обработку, нужно вернуться не на @@MidCycle, а в процедуру добавления новой точки, и на выдачу ЕЩЁ ОДНОГО задания, уже здесь.

Такое в цикл хрен загонишь, так что "развернём" эти проверки:

	;первым делом, проверяем, не сливается ли с пятном слева
	Acc 		[SP+1]
	SUB		[X+2j+k]
	[SP]		Acc
	DIV2S		D1
	DIV2S		[X+1]
	Z		[X+k]		;указатель на пятно "справа"
	JL		@@LeftMerge	;сейчас процедура слияния заметно усложнилась, приходится 2 отдельные ветви
					
	;если дошли досюда, значит с пятном слева не сливаемся, надо проверить теперь на пятно справа						
	Acc		[Z+2j+k]
	SUB		[SP+1]
	[SP]		Acc
	DIV2S		D1
	DIV2S		[Z+1]
	JL		@@RightMerge						

Здесь нам хотя бы не нужна строка ABS Acc, поскольку тут мы заранее знаем, как взять разность со знаком "плюс" (где пятно слева, а где справа). А также не нужен "i 1", "Z X" (чтобы Z указывал сначала на пятно слева, потом справа) и iLOOP, так что длина кода увеличилась только на 2 строки - и то радость...

Вслед за этими строками идёт код добавления нового пятна в список ActivePoints:

			;если попали сюда, значит слияния не было, и точку всё-таки надо добавить!
											
			;[SP+2j+1]=[SP+3] указывает яркость этой точки, [SP+2j]=[SP+2]: Y-координату, [SP+1]: X-координата
			;а куда вставить, указывает рег. X
			;в Acc содержится модуль разности между правой точкой и текущей, за вычетом двух радиусов
			Y		Heap									
			;добавит в X новую, пока что пустую точку.
			[SP++]	@@AfterListOp
						
;взять первый элемент из списка Y и перецепить его в начало списка X
;значения X,Y остаются неизменными,
;при вызове должно быть k=0, затираем регистр Z, Acc и флаг знака
;адрес возврата хранится в стеке, как положено
	ListOp proc			
		ZAcc	RoundZero
		Z	[Y+k]
		SUB	[Y+k]
		[Y+k]	[Z+k]
		JGE	@@OutOfMem									
		[Z+k]	[X+k]
		[X+k]	Z
		NOP	0
		JMP	[--SP]
@@OutOfMem:	[--SP]	Call(OutOfMemory)	;SP возвращается на место, но выпрыгиваем в другое место, на обработку ошибки
	ListOp endp						


Если помните, ListOp - "обособленная" процедура для перецепления элемента из одного списка в другой. Под такое подпадает и добавление новой точки (элемент перецепляется из Heap - списка "свободных" элементов - в ActivePoints), и удаление (элемент перецепляется назад в Heap), и собственно перецепление из ActivePoints в AllPoints.

Но мы в очередной раз пожадничали и включили процедуру в одно из мест, где она нужна, заменив её вызов CALL ListOp на весёлую строчку
[SP++]   @@AfterListOp

занося в адрес возврата строку сразу за этим вызовом. А именно что "прыгать" внутрь процедуры здесь не надо - переходим на неё "своим ходом".

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

Так что во варианте "Без AUP", начало несколько дополним:
			;если попали сюда, значит слияния не было, и точку всё-таки надо добавить!
			;но сначала проверим, нет ли у нас "долга" за предыдущую точку?
			Y		@@NewBlob
			JMP		@@TaskPending
											
			;[SP+2j+1]=[SP+3] указывает яркость этой точки, [SP+2j]=[SP+2]: Y-координату, [SP+1]: X-координата
			;а куда вставить, указывает рег. X
			;в Acc содержится модуль разности между правой точкой и текущей, за вычетом двух радиусов
@@NewBlob:		Y		Heap									
			;добавит в X новую, пока что пустую точку.
			[SP++]		@@AfterListOp


Пока так, потом, возможно, TaskPending ровно сюда и перенесём, избавившись от JMP :)

После перецепления списков (добавления нового элемента в список) идёт следующий код:
	;если добрались досюда, значит памяти хватило. X содержит адрес указателя на новую точку, а вот Z содержит адрес самой точки!
	;наполним её содержимым!						
	@@AfterListOp:	X	Z		;для дальнейшей работы (после MidCycle)... Чтобы мы не взялись за только что добавленную точку!
			[Z+1]	D1		;гориз. размер точки (будет расти при слияниях, а поначалу D, т.к мы сюда включаем и )																														
			[SP++]	@@MidCycle	;после вызова AcqQueue возвращаемся
						;сразу на метку @@MidCycle

;"заказать" видеопроцессору два отрезка на обработку,
;первый - на поиск новой точки (т.е здесь мы пока не ожидаем ничего найти),
;второй - на уточнение координат существующей
;в [SP+1], теперь уже [SP], лежит X-координата
;в [SP+2j]=[SP+2], теперь уже [SP+1] - Y-координата точки,
;в [SP+2j+1]=[SP+3], теперь уже [SP+2j]=[SP+2] - яркость точки
;при вызове AcqAndUpdate обновим значения, при вызове AcqNoUpd - не будем

;в [X+1] лежит радиус точки,
;в [X+2j+k]=[X+2] - X-координата
;в [X+2j+1]=[X+3] - Y-координата
;в [X+4j+k]=[X+4] - яркость
	AcqAndUpdate proc	
			i		2
			NOP		0	;избежать Hazard, ведь i участвует в следующей строке
	@@updCycle:	[X+2j+i]	[SP+i]
			iLOOP		@@updCycle
	AcqNoUpd:	Acc		[X+2j+k]
			DIV2S		[X+1]	;теперь в аккумуляторе у нас X - Ceil(D/2)
			ACQ		Acc		;первый отрезок
			ADD		[X+1]	;а вот теперь X + Floor(D/2)
			ACQ		Acc		;второй отрезок
			JMP		[--SP]
	AcqAndUpdate endp	


Снова тот же трюк с процедурой AcqAndUpdate - ровно здесь при её вызове не используется прыжок, что немножко экономит такты на предположительно "самом длинном пути выполнения".

Тут опять же ничего менять не надо, разве что нужно присмотреться повнимательнее к AcqAndUpdate: может, именно её вызывать внутри TaskPending, непосредственно для "озадачивания" видеопроцессора?

Между AcqAndUpdate и @@MidCycle мы и разместим метки @@LeftMerge и @@RightMerge, чтобы после них "своим ходом" попадать в @@MidCycle. Начнём с более простого @@RightMerge. Ранее у нас "слияние" занимало всего одну строку:

@@DoMerge:	[Z+1]	[SP]	;пока так


то есть, из всех параметров пятна мы меняли только его размер, да притом умудрились задать размер вдвое меньше, чем надо! В [SP] у нас хранилось расстояние между центром пятна и только что обнаруженной точкой, лежащей вблизи этого пятна, и такое значение подходит в качестве РАДИУСА, но мы же условились хранить ДИАМЕТР!

Сейчас же нужно ещё чутоку хитрее: как указывалось здесь, диаметр обновляется по формуле D' = (X + D/2 - x), и координата - по формуле X' = x + D'/2.

Нельзя ли их как-то упростить? У нас к этому моменту в аккумуляторе лежит значение X - x - D/2 - D1/2, и оно меньше нуля. Прибавить D, а затем ещё D1/2 - и получим то, что надо, и тогда нам не нужно специально заносить в [SP] разность X-x (нет особого смысла, одну строку там добавим, одну здесь сэкономим). Получается как-то так:

@@RightMerge:	ADD	[Z+1]	;в аккумуляторе лежало x-X-D/2-D1/2. Теперь прибавили D, получили x-X+D/2-D1/2
		DIV2A	D1	;прибавили D1/2, получили x-X+D/2 - новый диаметр пятна
		[Z+1]	Acc	;ага, записали.


И теперь ещё X-координату подправляем. В принципе, прямо "в лоб" давайте, потом думать будем. Текущее значение x (где нашли яркую точку) по-прежнему лежит в [SP+1], куда мы его и клали в самом начале, диаметр пятна в [Z+1], а X-координата пятна - в [Z+2]. Получаем:
	;теперь подкорректировать X-координату
	DIV2		Acc
	ADD		[SP+1]
	[Z+2j+k]	Acc


Если у нас есть команда AUP, то здесь наша обработка завершена - спокойно переходим на @@MidCycle, поскольку мы подкорректировали координаты точки СПРАВА от себя, а до неё мы и так не дошли пока ещё! Если же такой команды нет, из-за чего мы пока не стали отправлять задание на обработку предыдущей точки, то самое время его всё-таки отправить:

JMP		@@TaskPending


(в регистр Y мы уже давно поместили адрес возврата, @@MidCycle, и с тех пор к нему не обращались).


Продолжение следует... Нам предстоит написать слияние с пятном слева от себя (либо пятно с точкой, либо два пятна между собой), а также процедуру TaskPending (для случая без AUP), а ещё добавить вариант слияния "снизу", ну и весь код целиком "причесать" и отладить... Чего-то тяжело идёт после каникул.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Я создал монстра!

    Вот нормальная счастливая пара разъёмов ОНЦ-БС-1-10/14-Р12-2-В и ОНЦ-БС-1-10/14-В1-2-В: У розетки кроме основного выступа, отмечающего "верх",…

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Ковыряемся с сантехникой

    Наконец-то закрыл сколько-нибудь пристойно трубы, подводящие к смесителю, в квартире в Москве: А в воскресенье побывал на даче, там очередная…

  • Мартовское велосипедное

    Продолжаю кататься на работу и с работы на велосипеде, а также в РКК Энергию и на дачу. Хотя на две недели случился перерыв, очередная поломка,…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 2 comments