nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Опять алгоритм обнаружения

Достал он меня, но надо доделывать, всё остальное фактически готово.

В прошлый раз, неделю назад, остановились на том, что компилятор неправильно воспринимал литералы с отрицательным знаком, например "Nil EQU -32768", из-за чего у нас не устанавливался правильно флаг TaskPending (о том, что мы ещё не отправили задания по предыдущему пятну), и всё рушилось.

Но когда компилятор поправили, программа снова не заработала нормально "в железе", приводя к "сбоям синхронизации", а под конец - опять к "исчерпанию заданий GPU". Поэтому ничего не остаётся, как запустить подправленную программу на симуляции и посмотреть, что там происходит.

Такая у нас картинка, 128х128, ч/б (1 бит):
Simulation1.png

и мы в порыве оптимизма начинаем со строки 14 (0x0E). Если начало прошло точно также, как прежде, у нас должно быть одно обнаруженное пятно (61;11) диаметром 3, и выданы задания на отрезки [0;59], [60;62], [63;127] и HSync. Сейчас поглядим, так ли это?




Приведём листинг кода, выполняемого на скриншоте:

22  F288  @@ActPointsStart:   [SP+2j+1]   GPUL            ;яркость самой яркой точки на отрезке
23  F08A                      [SP+1]      GPUH            ;соотв. координата
24  8011                      Acc         Threshold       ;поставили задом наперёд, чтобы избежать Hazard'а   
25  83F2                      SUB         [SP+2j+1]       ;вычитаем порог, положит. значение свидетельствует о новом найденном "пятне"                        
26  FC12                      [SP]        @@MidCycle
27  B813                      JL          TaskPending ;пятна нет, не торопимся заказывать отрезок
28  80CA                      Acc         [X+2j+k]
29  83F0                      SUB         [SP+1]
2A  8E01                      DIV2A       D1
2B  8EC0                      DIV2A       [X+1]
2C  EDC8                      Z           [X+k]
2D  BC14                      JGE         @@LeftMerge
2E  80EA                      Acc         [Z+2j+k]
2F  83F0                      SUB         [SP+1]
30  8F15                      DIV2S       D1p1
31  8FE0                      DIV2S       [Z+1]


Нашли яркий пиксель, яркость его пришла как 00, что означает FF (яркость у нас инвертируется), затем пришла его координата 0x3A = 58.

Загружаем в аккумулятор порог, 1, вычитаем текущую яркость, 0, получаем неотрицательный результат, поэтому переход JL TaskPending не срабатывает.

Проверяем, не надо ли эту точку отнести к пятну слева от себя. Загружается X-координата этого пятна ("левого фиктивного", коорд. -32768), вычитаем текущую координату, 0x3A, затем половинку "минимального диаметра" D1=3, и половинку диаметра левого фиктивного пятна. Затем кладём в Z адрес пятна справа от нашей точки, 0x0A0. Вспоминаем содержимое памяти:

ActivePoints:     09B  0x00A0
AllPoints:        09C  0x8000
APHeadDummyX:     09D  0x8000
Heap:             09E  0x00A4
APTailDummyX:     09F  0x7FFF
Elem0Next:        0A0  0x009D
Elem0D:           0A1  0x0003
Elem0X:           0A2  0x003D
Elem0Y:           0A3  0x000B
Elem1:            0A4  0x00A8
Elem1[1]:         0A5  ????
Elem1[2]:         0A6  ????
Elem1[3]:         0A7  ????


Да, вроде всё правильно.

Прыжок JGE @@LeftMerge не выполняется, и это правильно, к "фиктивным" пятнам ничего прилипать не должно! Они нужны лишь для того, чтобы не усложнять код лишними проверками "а вдруг слева и нет никакого пятна?"

Далее проверяем, не нужно ли отнести точку к пятну справа от неё. Вот это пятно вполне реально. В аккумулятор загружается его X-координата, 0x3D. Вычитается текущая координата, 0x3A, что даёт 3.

Следующий слайд!


Вычитаем (D1+1)/2, что даёт 1. Наконец, вычитаем диаметр правого пятна (3), делёный на 2, что даёт -0,5. Мы переходим на метку @@RightMerge:

64  82E0  @@RightMerge:   ADD         [Z+1]   ;в аккумуляторе лежало x-X-D/2-D1/2. Теперь прибавили D, получили x-X+D/2-D1/2
65  8E1D                  DIV2A       D1p2    ;прибавили D1/2, получили x-X+D/2 - новый диаметр пятна
66  E080                  [Z+1]       Acc     ;ага, записали.
67  8C80                  DIV2        Acc
68  82F0                  ADD         [SP+1]
69  8311                  SUB         1
6A  EA80                  [Z+2j+k]    Acc
6B  B013                  JMP         TaskPending


Прибавляем к значению в аккумуляторе (-0,5) диаметр правого пятна, 3, получаем 2,5. Затем прибавляем (D1+2)/2, получается 5. Заносим это значение как новый диаметр пятна. Снова делим пополам, получая 2,5. Прибавляем текущую X-координату, 0x3A, получая 60,5. Вычитаем единичку, получая 59,5. При сохранении в память дробная часть пропадает, итого новая X-координата центра пятна: 0x3B = 59.

И прыгаем в TaskPending:


Листинг TaskPending:
    TaskPending proc
34  8483              ABS     C
35  BEFC              JNO     [SP]        ;вот в чём прелесть стека без инкремента!
36  80CA  AcqNoCheck: Acc     [X+2j+k]
37  8FC0              DIV2S   [X+1]   ;теперь в аккмуляторе у нас X - Ceil(D/2)
38  8E11              DIV2A   1   ;чтобы всё-таки было X-Floor(D/2)
39  2080              ACQ     Acc     ;первый отрезок
3A  82C0              ADD     [X+1]   ;а вот теперь X + Floor(D/2)
3B  2080              ACQ     Acc     ;второй отрезок
3C  B0FC              JMP     [SP]
    TaskPending endp    


Надолго мы тут не задерживаемся. Берём абсолютное значение от C=0, получаем ожидаемо 0, никакого переполнения, поэтому срабатывает переход JNO [SP]. В [SP] мы ранее занесли метку @@MidCycle. Туда мы и попадаем:

71  CDC8  @@MidCycle:     X           [X+k]
72  DDCD                  Y           X
73  84C8                  ABS         [X+k]
74  BA0F                  JO          @@FinalRange
75  F288  @@EndOfCycle:   [SP+2j+1]   GPUL            ;яркость
76  F08A                  [SP+1]      GPUH            ;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 
77  8A0B                  C           Nil         ;по умолчанию ставим метку "за нами должок!"                
78  80C2                  Acc         [X+2j+1]
79  8EC0                  DIV2A       [X+1]
7A  83FA                  SUB         [SP+2j+k]
7B  BC1E                  JGE         @@ActPointsStart
7C  831F                  SUB         nD1
7D  B820                  JL          @@RemoveBlob


В регистр X заносим адрес пятна, 0xA0. А в регистр Y - старое значение X, адрес левого фиктивного пятна 0x9B (оно пригодится, если текущее пятно захотим перенести в другой список). Проверяем, что имеем дело с РЕАЛЬНЫМ пятном, а не правым фиктивным, для чего берём модуль (абсолютное значение) от адреса следующего пятна, 0x9D. Ожидаемо это не приводит к переполнению (только значение -32768 даст переполнение от команды ABS), поэтому в @@FinalRange пока не прыгаем.

Вместо этого получаем результаты по отрезку [60;62]: макс. яркость 0 (то есть максимальная), координата самого яркого пикселя: 0x3C = 60. Да, когда на отрезке много пикселов с максимальной яркостью, берётся самый первый, всё работает ровно так, как мы это спроектировали.

В регистр C помещается значение 0x8000, он же -32768 - НАКОНЕЦ-ТО! В прошлый раз здесь была ошибка, а сейчас всё правильно.

Далее проверяем, относится ли текущая строка изображения к этому пятну, или оно так далеко вниз не простирается. Для этого помещаем в аккумулятор Y-координату центра пятна, 0xB = 11. Прибавляем половину его диаметра, 5, что должно дать 13,5. Вычитаем номер текущей строки, 0xC = 12, что должно дать 1,5. Это неотрицательное значение, поэтому срабатывает JGE @@ActPointsStart - мы решили пока оставить пятно на своём месте, что и логично, всего на прошлой строке его обнаружили!

И мы переходим к следующему отрезку, [63;127]. Получаем максимальную яркость, 0 (т.е 255) и координату 0x3F = 63. Логично, пятно большое, и мы опять взяли крайнее левое значение.

Следующий слайд:


Проверяем, что яркость выше порога - разумеется. И далее проверяем, нужно ли этот пиксель отнести к пятну слева от себя. Загружаем X-координату пятна, 59. Вычитаем текущее значение, 63, получается -4. Прибавляем D1/2, получается -2,5. Прибавляем половинку диаметра этого пятна, 5, получается ровно 0 - неотрицательное значение.

Вот только JGE @@LeftMerge не выполняется! И задним числом понимаешь, почему: команды DIV2A не меняют флаг знака, только SUB меняет. Поэтому переход на @@LeftMerge в принципе никогда не может выполниться! И это многое объясняет, у нас рождаются точки, налезающие друг на друга - и пошло-поехало!

Всё, что нужно - это поменять порядок строк:

	;первым делом, проверяем, не сливается ли с пятном слева			
	Acc	[X+2j+k]
	DIV2A	D1
	DIV2A	[X+1]
	SUB	[SP+1]
	Z	[X+k]
	JGE	@@LeftMerge


DIV2S (вычесть значение делёное на два), как мы видели в начале этого поста, знак сменяет. Видимо, поначалу так оно и было, а потом я решил чуть "смягчить условие", поменяв знаки, и забыл о своей же "фиче", где знак меняет только вычитание из аккумулятора, но не прибавление к нему!

Ладно, сейчас откомпилим исправленный код - и опробуем его для начала на "железе", вдруг прям возьмёт и заработает!

Нет, опять "исчерпание заданий GPU", но в этот раз протянули куда дольше:



Ещё одной ошибкой меньше, но какая-то пакость там ещё осталась...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Формулы приведения, что б их... (и atan на ТРЁХ умножениях)

    Формулу арктангенса на 4 умножениях ещё немножко оптимизировал с помощью алгоритма Ремеза: Ошибка уменьшилась с 4,9 до 4,65 угловой секунды, и…

  • Алгоритм Ремеза в экселе

    Вот и до него руки дошли, причина станет ясна в следующем посте. Изучать чужие библиотеки было лениво (в том же BOOSTе сам чёрт ногу сломит), писать…

  • atan на ЧЕТЫРЁХ умножениях

    Мишка такой человек — ему обязательно надо, чтоб от всего была польза. Когда у него бывают лишние деньги, он идёт в магазин и покупает какую-нибудь…

  • Ай да Пафнутий Львович!

    Решил ещё немного поковыряться со своим арктангенсом. Хотел применить алгоритм Ремеза, но начал с узлов Чебышёва. И для начала со своего "линейного…

  • atan(y/x) на двух умножениях!

    Чего-то никак меня не отпустит эта тема, всё кажется, что есть очень простой и эффективный метод, надо только его найти! Сейчас вот такое…

  • Таблица коэффициентов для atan1

    Пора уже добить этот несчастный арктангенс, что-то слишком долго его ковыряю. Мы упоминали, что в оперативной памяти будет лежать таблица в 15 слов:…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments