nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Тестирование поиска "центральных" точек

У меня, конечно, ещё "обнаружение" ждёт своего часа, но сейчас уже словил азарт по написанию алгоритма ближней дистанции. Так что уж помучаю его.

В очередной раз QuatCoreImmTable доставила хлопот - чуть-чуть поменялось, значений стало больше, и CANNOT FIND FIT. Поэтому пока что заменил на QuatCoreImmROM - там эта таблица просто как блок памяти объявлена. Вот тогда всё моментально отсинтезировалось в 511 ЛЭ - это "голое ядро" без видеопроцессора и прочей периферии.

Ну и запускаем симуляцию.



Разумеется, тут ничего не поймёшь без листинга (первые этапы, уже пройденные, не стал здесь приводить):
FindCentralPoints proc
2B  F3B4                  [SP++]      Call(FindCentralPoint)  ;классический вызов процедуры, т.к она использует стек [SP] и [SP+1], недопустимо чтобы затёрла адрес возврата
2C  FCB8                  [SP]        Call(SwapPoints)        ;вызов без инкремента стека, чтобы можно было в неё запрыгивать из условных переходов, зная что SP останется где надо
2D  A70F                  ijk         0x00A5  ;{Inv, k, i, j} когда-нибудь надо ввести синтаксис, чтобы указывать биты don't care, чуть поможет компилятору
2E  FCB8                  [SP]        Call(SwapPoints)
2F  F3B4                  [SP++]      Call(FindCentralPoint)
30  A110                  j           3
31  FCB8                  [SP]        Call(SwapPoints)
FindCentralPoints endp
32  B011  endless:        JMP endless
FindCentralPoint proc
33  A712                  ijk         0x04C5  ;одним махом всех иниц. {Inv, k, i, j}
34  8A13  @@k_loop:       C           25933       ;число 0,7914 в формате Q1.15
35  90C9                  MUL         [X+2i+k]    ;Fy6 на первой итерации, Fx6 на второй
36  8A14                  C           6835        ;число 0,2086 в формате Q1.15
37  92E9                  FMA         [Z+2i+k]    ;Fy7 на первой итерации, Fx7 на второй
38  D880                  [Y+k]       Acc
39  AA15                  kLOOP       @@k_loop
3A  F016                  [SP+1]      32767       ;текущий минимум, инициализируем максимальным значением
3B  A204  @@outer_cycle:  k           1
3C  FC03                  [SP]        0       ;сумма квадратов
3D  8900                  NOP         0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
3E  80CA  @@inner_cycle:  Acc         [X+2j+k]    ;Fy[i] если k=1,  Fx[i] если k=0
3F  83D8                  SUB         [Y+k]       ;Cy если k=1, Cx если k=0
40  9C80                  SQRD2       Acc
41  82FC                  ADD         [SP]
42  FC80                  [SP]        Acc
43  AA17                  kLOOP       @@inner_cycle
44  83F0                  SUB         [SP+1]
45  BC18                  JGE         @@skip
46  F0FC                  [SP+1]      [SP]
47  A0A1                  i           j
48  A919  @@skip:         jLOOP       @@outer_cycle
49  B0FF                  JMP         [--SP]  ;ret
FindCentralPoint endp
SwapPoints  proc
4A  A204                  k           1
4B  8900                  NOP         0   ;хотим избежать warning'ов
4C  8AEA  @@swap:         C           [Z+2j+k]
4D  EAC9                  [Z+2j+k]    [X+2i+k]
4E  C983                  [X+2i+k]    C
4F  AA1A                  kLOOP       @@swap
50  B0FC                  JMP         [SP]
SwapPoints  endp    


Мы видим, как вызывается процедура FindCentralPoint, при этом на шину данных поступает адрес возврата, 0x2C. Далее инициализируем разом все индексные регистры i,j,k (i=6, k=1, j=5), а в регистр C заносим страшное число 0x654D = 25933, что в нашем формате Q1.15 означает 0,79141. Теперь ещё приведём дамп памяти после этапа сортировки. В той записи, как оказалось, я дамп не вставил, вместо него случайно ещё одну "осциллограмму", но сейчас поправил, и здесь повторю:

sortDump.png

Итак, значение 0,79141 мы умножаем на 0xD340 = -11456, это Fy6. Затем в регистр C заносим новый коэффициент 0x1AB3 (они в сумме с 0x654D как раз дадут 0x8000), и умножаем его на 0xAEC0 = -20800, это Fy7.

Результатом становится 0xCBA3 = -13405. Если посчитать "ручками" -11456*0,79141 - 20800*(1-0,79141), получим именно это. Замечательно! Этот результат заносится в память, и тут же переходим в начало цикла, чтобы теперь посчитать координату X центра.

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


В этот раз на 0,79141 умножаем Fx6 = 29376, затем прибавляем 0,20859 умноженный на Fx7 = -25664. Результатом становится 17895 = 0x45E7, всё верно, его тоже заносим в память.

Начинаем подготовительную работу к циклам: "минимум" инициализируем большим значением 32767, k=1, [SP]=0, потом ещё и NOP "выполняем".

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


В аккумулятор заносим Fy5 = 0xAF00 = -20736 . Вычитаем 0xCBA3 = -13405 (y-координата центра), результат возводим в квадрат, делим пополам и прибавляем [SP]=0. Результатом становится 820 = 0x0334, всё верно. Этот результат заносится назад в [SP] и выполняем вторую итерацию по k. Там мы заносим Fx5 = 0xB6C0 = -18752 , вычитаем 0x45E7 = 17895 (x-координата центра), и результатом становится 0x8000 = -32768, то есть ПРОИСХОДИТ НАСЫЩЕНИЕ РЕЗУЛЬТАТА. В данном случае, не вижу ничего криминального: ведь мы ищем МИНИМУМ, и он явно не должен будет войти в насыщение. А если самые большие результаты в дверь не пролазят и несколько обрезаются - ну и пускай :)

В итоге, этот -32768 возводится в квадрат и делится на 2, давая 16384 = 0x4000. Следующий слайд:


Да, мы прибавляем [SP] = 0x334 и получаем 0x4334, всё логично. Сейчас посмотрим, правильно ли обновляется минимум?

Выходим из цикла по k, вычитаем из аккумулятора 0x7FFF = 32767 (наш "текущий минимум"), результат явно выходит отрицательным, и переход JGE не выполняется. Вместо этого заносим в [SP+1] наш новый минимум, 0x4334, а в регистр i - индекс, на котором этот минимум был достигнут, 5.

И возвращаемся в начало цикла по j.

Выглядит очень неплохо. Давайте промотаем все остальные итерации. Возврат из процедуры FindCentralPoint мы должны заметить, там мы прыгнем в PC=0x2C:


По последней итерации можно заметить, что минимум наступил именно на ней, при i=0, и минимум равен 0x0163 = 355. Это соответствует дистанции в 4823 единицы, которые у нас равны 1/64 пикселя, то есть 75 пикселей. Похоже на правду. Вспомним, как всё это располагалось:

sort01.png

И пока что для нас "левая" центральная точка означает - расположенная вблизи крайней точки под номером 6. И да, это и должна была оказаться точка под индексом 0. Причём здесь она действительно отодвинута от центра, на те самые 50..75 пикселей, что мы и насчитали.


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

  • Тестируем atan1 на QuatCore

    Пора уже перебираться на "железо" потихоньку. Решил начать с самого первого алгоритма, поскольку он уже был написан на ассемблере. В программу внёс…

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

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

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

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

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

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

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

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

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

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments