Сообщество

krufter_multiclet, оптимизированную, это какая имеется в виду?

Так-то всё здесь: https://bitbucket.org/qewerty/qf/overview. Там лучшая реализация, которая у меня получилась. Всё, что начинается c qf_mat44_mul*: в qf_mat44_mul.s сама функций, qf_mat44_mul_BENCH.s - цикл её использующий, qf_mat44_mul_TEST.c - сишная запускалка.

Модель для windows обновлена, для Linux выложу чуть позже.
qewerty, спасибо за ссылку.

qewerty wrote:

Так-то всё здесь: https://bitbucket.org/qewerty/qf/overview. Там лучшая реализация, которая у меня получилась. ...

Здравствуйте, периодически заглядываю в ваш репозиторий :)

Появились некоторые замечания и предложения по файлу "qf_mat44_mul.s" :

• Если во время выполнения первого параграфа "qf_mat44_mul:" произойдёт прерывание (на него ведь можно повесить внешнюю подпрограмму использующую стек?), то может перезаписываться стек с сохранёнными регистрами (#32, #33, #34), т.к. #SP в программе не меняется. Поэтому немного подправил код (см. ниже). Исходил из того, что значения регистров по команде "setl" меняются после "complete" (надеюсь понял правильно).

• Ещё предлагаю разбить блок "Вспомогательные значения для упаковки матрицы a в строки" на 2 части. Т.к. считывание в @vaCD и @vaEF и их использование находятся слишком близко.
  Хотя, скорее всего это никак не повлияет на производительность, если ВСЕ предыдущие команды выполняются за 1 такт и распределение по клеткам МП происходит подряд циклически от начала параграфа, то если посчитать, то вроде пройдёт нормально. Но пока точно не установлено, что все команды за 1 такт, то лучше поставить чуть подальше :)

• Тут возник ещё один вопрос. Может разнести между собой команды типа:
  rdl #SP
  jmp @1
  Теоретически у них есть зависимость и, следовательно, одна клетка вначале будет ждать результата другой.

• + Немного поправил комментарии.

Можете протестировать?

Чтобы быстрее разобраться со стеком нарисовал картинку:¶

Show Hide

.include "qf_common.inc" 

.text

; Си-прототип:
;   void qf_mat44_mul(const float* a, const float* b, float* c);

; Оптимизации:
;  * для 4-х клеточного МП - MCp0411100101

.global qf_mat44_mul
qf_mat44_mul:
    .alias qf_mat44_mul.a #SP,4
    .alias qf_mat44_mul.b #SP,8
    .alias qf_mat44_mul.c #SP,12
    .alias qf_mat44_mul.old_i32 #SP,-4
    .alias qf_mat44_mul.old_i33 #SP,-8
    .alias qf_mat44_mul.old_i34 #SP,-12

    .alias qf_mat44_mul.stackb 12      ; Количество байт под стек. #BP(#38) не используется.
    .alias qf_mat44_mul.old_i32.newSP #SP,8
    .alias qf_mat44_mul.old_i33.newSP #SP,4
    .alias qf_mat44_mul.old_i34.newSP #SP

    jmp qf_mat44_mul.P0

    ; выделяем наш кадр стека. Часть 1 из 3
    SP13 := getl #SP
    ; сохранение адресов аргументов в регистрах
    a := rdl qf_mat44_mul.a
    b := rdl qf_mat44_mul.b
    c := rdl qf_mat44_mul.c
    ; выделяем наш кадр стека. Часть 2 из 3
    SP23 := subl @SP13, qf_mat44_mul.stackb
    ; Получение значений регистров 32, 33 и 34
    old_i32 := getl #32
    old_i33 := getl #33
    old_i34 := getl #34
    ; выделяем наш кадр стека. Часть 3 из 3
    setl #SP, @SP23
    ; Запись в индексные регистры указателей на аргументы
    setl #32, @a
    setl #33, @b
    setl #34, @c
    ; Сохранение старых значений индексных регистров в стеке
    wrl  @old_i32, qf_mat44_mul.old_i32
    wrl  @old_i33, qf_mat44_mul.old_i33
    wrl  @old_i34, qf_mat44_mul.old_i34
complete

.local qf_mat44_mul.P0
qf_mat44_mul.P0:
    ; следующий параграф. Часть 1 из 2
    exit := rdl #SP, qf_mat44_mul.stackb
    ; Чтение матрицы "a" 
    va01 := rdq #32
    va23 := rdq #32,8
    va45 := rdq #32,16
    va67 := rdq #32,24
    va89 := rdq #32,32
    vaAB := rdq #32,40
    vaCD := rdq #32,48
    vaEF := rdq #32,56
    ; следующий параграф. Часть 2 из 2
    jmp @exit
    ; Вспомогательные значения для упаковки матрицы "a" в строки. Часть 1 из 2
    va54 := pack @va45, @va45
    va76 := pack @va67, @va67
    ; Чтение матрицы "b" 
    vb01 := rdq #33
    vb23 := rdq #33,8
    vb45 := rdq #33,16
    vb67 := rdq #33,24
    vb89 := rdq #33,32
    vbAB := rdq #33,40
    vbCD := rdq #33,48
    vbEF := rdq #33,56
    ; Вспомогательные значения для упаковки матрицы "a" в строки. Часть 2 из 2
    vaDC := pack @vaCD, @vaCD
    vaFE := pack @vaEF, @vaEF
    ; Упаковка строк матрицы "a" 
    va04 := patch @va45, @va01
    va8C := patch @vaCD, @va89
    va15 := pack @va54, @va01
    va9D := pack @vaDC, @va89
    va26 := patch @va67, @va23
    vaAE := patch @vaEF, @vaAB
    va37 := pack @va76, @va23
    vaBF := pack @vaFE, @vaAB
    ; Скалярные произведения строк матрицы "a" со столбцами матрицы "b".
    ; Сначала находим все промежуточные компоненты потоком независимых инструкций.
    ; Ниже вычисляем все суммы. На процессоре MCp0411100101 так получается
    ; несколько быстрее, чем вычисление каждого скалярного произведения подряд.
    madd @va04, @vb01
    madd @va8C, @vb23
    madd @va15, @vb01
    madd @va9D, @vb23
    madd @va26, @vb01
    madd @vaAE, @vb23
    madd @va37, @vb01
    madd @vaBF, @vb23
    madd @va04, @vb45
    madd @va8C, @vb67
    madd @va15, @vb45
    madd @va9D, @vb67
    madd @va26, @vb45
    madd @vaAE, @vb67
    madd @va37, @vb45
    madd @vaBF, @vb67
    madd @va04, @vb89
    madd @va8C, @vbAB
    madd @va15, @vb89
    madd @va9D, @vbAB
    madd @va26, @vb89
    madd @vaAE, @vbAB
    madd @va37, @vb89
    madd @vaBF, @vbAB
    madd @va04, @vbCD
    madd @va8C, @vbEF
    madd @va15, @vbCD
    madd @va9D, @vbEF
    madd @va26, @vbCD
    madd @vaAE, @vbEF
    madd @va37, @vbCD
    madd @vaBF, @vbEF
    vc0 := addf @32, @31
    vc1 := addf @31, @30
    vc2 := addf @30, @29
    vc3 := addf @29, @28
    vc4 := addf @28, @27
    vc5 := addf @27, @26
    vc6 := addf @26, @25
    vc7 := addf @25, @24
    vc8 := addf @24, @23
    vc9 := addf @23, @22
    vcA := addf @22, @21
    vcB := addf @21, @20
    vcC := addf @20, @19
    vcD := addf @19, @18
    vcE := addf @18, @17
    vcF := addf @17, @16
    ; Запись результатов,
    ;   "wrl" тут работает чуть быстрее, чем упаковка и запись с "wrq".
    wrl @vc0, #34
    wrl @vc1, #34,4
    wrl @vc2, #34,8
    wrl @vc3, #34,12
    wrl @vc4, #34,16
    wrl @vc5, #34,20
    wrl @vc6, #34,24
    wrl @vc7, #34,28
    wrl @vc8, #34,32
    wrl @vc9, #34,36
    wrl @vcA, #34,40
    wrl @vcB, #34,44
    wrl @vcC, #34,48
    wrl @vcD, #34,52
    wrl @vcE, #34,56
    wrl @vcF, #34,60

    ; убираем наш кадр стека. Часть 1 из 3
    SP13 := getl #SP
    ; Восстановление старых значений индексных регистров. Часть 1 из 2
    old_i34 := rdl qf_mat44_mul.old_i34.newSP
    old_i33 := rdl qf_mat44_mul.old_i33.newSP
    old_i32 := rdl qf_mat44_mul.old_i32.newSP
    ; убираем наш кадр стека. Часть 2 из 3
    SP23 := addl @SP13, qf_mat44_mul.stackb
    ; Восстановление старых значений индексных регистров. Часть 2 из 2
    setl #34, @old_i34
    setl #33, @old_i33
    setl #32, @old_i32
    ; убираем наш кадр стека. Часть 3 из 3
    setl #SP, @SP23
complete

1)Если вы подключаете к проекту crt0.o, то стек после прерывания и выхода из обработчика не изменится по сравнению с состоянием стека до прерывания.
Если вы не подключаете к проекту crt0.o, то работу со стеком берёте на себя.

2)Это можно проверить, вы можете записаться на любое удобное для вас время(можно и на большее чем обычно время) для удалённого тестирования.

3)Да если параграф имеет много команд, то разнесение может немного улучшить результат.

krufter_multiclet, Модель для windows обновлена, для Linux выложу чуть позже.

Очень хочется Linux'овую :) И где её потом искать? Под win самая свежая от 15.07.

Модель для Linux доступна по ссылке:

http://multiclet.com/community/attachments/download/93/(linux)mc-model.7z

Модель для Windows доступна по ссылке:

http://multiclet.com/community/attachments/download/94/(win)mc-model.7z

Все самые свежие обновления доступны тут:

http://multiclet.com/community/projects/examples/files

Спасибо, всё заработало в модели!

Ещё очень не хватает в выводе mc-model видеть текущий адрес инструкции, особенно это полезно после условных переходов:

$ mc-model -d -inst-asm -inst-render -inst-strange -dump-raw -dump-addr -dump-byte -dump-symbol -dump-length 4 -dump-from 0x00000000 image.bin

PM1:
  i=31
  jmp 0x82;  ir = 7a08000000000082  opcode=1e   suf=2  type=0  F1=0  F2=0 V=82       arg1=3   arg2=82  *sb=82  flag.f=0
   0.0000000000000082 <= 0000000000000003, 0000000000000082 :  cop= 1E sfx= 2 top= 0 cmp= 1 tau= 0 F1=  0 F2=  0 : jmp    0x82
--- complete ---------------------

PM0:
  i=32
  rdq #20;   ir = 8532202000000000  opcode=21   suf=1  type=3  F1=0  F2=20 V=0       arg1=3   arg2=88  *sb=35f7c1b6e08d29a4  flag.f=0
   0.35f7c1b6e08d29a4 <= 0000000000000003, 0000000000000088 :  cop= 21 sfx= 1 top= 3 cmp= 0 tau= 22 F1=  0 F2= 20 : rdq    #20

PM1:

Ещё mc-model был застукан:

$ strace -fF /usr/local/bin/mc-model -interactive image.bin
[…]]
close(3)                                = 0
open("//tmp//dbg_pipe_sout", O_RDONLY)  = -1 ENOENT (No such file or directory)
read(4294967295, 0x8178f60, 13)         = -1 EBADF (Bad file descriptor)
read(4294967295, 0x8178f60, 13)         = -1 EBADF (Bad file descriptor)

[pid  9088] clone(Process 9089 attached
child_stack=0, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f6f9d46c9d0) = 9089
[pid  9088] exit_group(0)               = ?
Process 9088 detached
[pid  9087] <... sync resumed> )        = ? ERESTART_RESTARTBLOCK (To be restarted)
[pid  9087] --- SIGCHLD (Child exited) @ 0 (0) ---
[pid  9087] restart_syscall(<... resuming interrupted call ...> <unfinished ...>
[pid  9089] --- SIGSEGV (Segmentation fault) @ 0 (0) ---
Process 9089 detached
<... restart_syscall resumed> )         = 0
pipe2([5, 6], O_CLOEXEC)                = 0

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

Ещё очень не хватает в выводе mc-model видеть текущий адрес инструкции, особенно это полезно после условных переходов:

Данное пожелание учтено, как появится время, так оно и реализуется в модели.

В текущей версии сначала запускается отладчик, который создаёт пайпы

В том-то и дело, что он их не создаёт, а пытается открыть только на запись и только один из двух и только после попытки запустить mc-model.

Т.е. никакую программу не получалось отработать с помощью отладчика? Или это только на конкретной программе?

Если удалить файлы /tmp/dbg_pipe_s{out,in} и запустить:

$ mc-dbg --mode model image.bin

Multiclet Corp. Debugger v 0.5.0
MC-MODEL was started ...
Connection with mc-model BAD...

Падает и не работает. Если же создать вручную пайпы перед запуском:

$ mkfifo /tmp/dbg_pipe_s{in,out}
$ mc-dbg --mode model image.bin

Multiclet Corp. Debugger v 0.5.0
MC-MODEL was started ...
Connection with mc-model GOOD...

…то всё отлично.

Под strace'ом видно как сначала стартует модель и падает в корку (иногда видно, что после безуспешной попытки открыть пайп), а затем mc-dbg также безуспешно пытается открыть второй пайп только на запись:

open("//tmp//dbg_pipe_sout", O_WRONLY) = -1 ENOENT (No such file or directory)

• image-enc.bin выполняет gost_encode и вешается на gost_decode
• image-dec.bin сразу вешается на gost_decode

Посмотрю в ближайшее время.

А в этом параграфе всё нормально?

gost.save_results:
    rdl #SP, 12
newp :=    addl @1, 4
    getl #BB
    getl #AA
    wrl @2, @4    /* Сохраняем новые значения в буфере */
    wrl @2, @4
    wrl @newp, #SP, 12 /* Сохраняем новый указатель в стеке */
    jmp gost.next_block
complete

Тут вы два раза пишете по одному адресу в середине и в конце. В принципе при первом просмотре не заметил где стек портится.

Я уже это место переписал с использованием локальной переменной. Проблема, видимо, где-то ещё %) Я же могу из функции изменить содержимое по указателю, переданному через стэк, в частности, изменить содержимое массива? Странности в этом куске есть. Если закомментировать:

wrl @newp, BufPtr

То из функции уже получается вернутся и не раз, только значения, вычитываемые из адреса начального буфера (_buf @ 0xc8) совсем не те. В симуляторе, вроде, всё ок. Параметры дальше тоже передавались нормальные, насколько я смог разобрать.

На реальном железе в терминале вижу вместо:

System is booting...
629D1FC2, B61F9AA0enc={629D1FC2, B61F9AA0}
dec={629D1FC2, B61F9AA0}

System is booting...
629D1FC2, B61F9AA0enc={629D1FC2, B61F9AA0}
dec={629D1FC2, B61F9AA0}
enc={, }
dec={, }

Завтра проанализирую ещё раз код посмотрим где ошибка и кто портит стек. Содержимое массива вы менять можете, вычитав из стеке адрес массива.

Добавил а-ля шелл. Команды:

print — вывод текущего значения буфера
encode — шифрование
decode — расшифровывание
enc-print — шифрование и вывод результата
dec-print — расшифровывание и вывод результата

aa=b61f9aa0 bb=629d1fc2
aa=ed7e2975 bb=d48f796f
aa=7afe35fe bb=1de5ecf9
aa=ef90cb87 bb=c47ddb72

{629D1FC2, 9A1F9AA0}
{ECECFDF5, 9AA06670}
{34856A37, 9A74F7C0}

mouse, вы свою программу по ГОСТ доделали?
Я тут посмотрел вашу реализацию из "test-gost-7.tar.gz", в ASM реализации неверно сделаны циклы по параграфам и ещё несколько неточностей.
А у вас main.c нормально компилируется? Вроде текущий компилятор не поддерживает формат 64 бита и Sblock интерпретируется неверно (+ адресация к массиву). Вы уверены, что у вас считает в модели нормально?

Попозже выложу поправленный тестовый код на С и ASM.

Модель работает как часы. На реальном железе есть проблемы.
В чём некорреткность циклов и какие неточности?

Вроде текущий компилятор не поддерживает формат 64 бита и Sblock интерпретируется неверно

Причём здесь Sblock (local), который определён в ассемблерном коде и компилятор Си?

Вы уверены, что у вас считает в модели нормально?

Конечно, проверял пошагово.
PS. прикладываю посвежее версию.

Ой, да я неверно написал имя файла, я имел ввиду файл "t.c", в нём есть sblock. За основу взял этот файл и анализировал как реализовано у вас для ASM. Поправил ваш файл и немного сделал в другом формате, а то немного неудобно было ставить метки. Назвал "gost_2.asm"

К сожалению ваша ASM реализация у меня на модели ("MultiCletSDK_ru.20130814.exe") уходит в цикл, а на новом "MultiCletSDK_ru.20130906.exe" выходит с ошибкой по обращении к памяти.

• gost.load_key1_24 - всегда прыгает на gost.round
• gost.load_key25_32 - всегда прыгает на gost.round
• gost_enc.epilogue - несколько условий перехода, которые могут одновременно быть истинными (? уточнить) (в модели возможно переход будет по последнему обработанному, а на железе неизвестно)
• gost_dec.epilogue - несколько условий перехода, которые могут одновременно быть истинными (? уточнить) (в модели возможно переход будет по последнему обработанному, а на железе неизвестно)
• gost.save_results - новый указатель должен быть ещё на 4 больше
• нет сохранения используемых регистров

По поводу gost_enc.epilogue и gost_dec.epilogue тут надо уточнить:

...
        if (j != 0)
           key1_24(idx);
        if (xor != 0)
           key25_32(idx);
...

• компилятор некорректно обрабатывает массив sblock, если посмотреть в ASM файле, то там часть данных = "0xFFFFFFFF" (проверял на "MultiCletSDK_ru.20130814.exe")
• в void gost_round(): "fAiKi |= ((sblock[i] >> (((axk >> (i*4)) & 0xf) << 2)) & 0xf) << (i*4);" должно быть обращение к данным sblock[i] как 64 бита? Если да, то тут тоже немного неверно (опять компилятор). Поэтому дописал отдельную функцию slr64.

Возможно я что-то напутал или неправильно понял в реализации, так что прошу сильно не быть :)

Если нормально заработает, то можно будет подумать как дополнительно оптимизировать.

Файл t.c не используется в сборке — это эталон на Си под gcc. (в коде встречается множественный printf и наколенный ROL вместо одной ассемблерной инструкции).

gost.load_key1_24 - всегда прыгает на gost.round
gost.load_key25_32 - всегда прыгает на gost.round

В конце параграфа мы обязаны куда-то перейти. Перед вызовом gost.round нам надо подгрузить следующий ключ Ki из последовательности 32-х ключей. Не очень понял в чём особенность.

gost_enc.epilogue - несколько условий перехода, которые могут одновременно быть истинными (? уточнить) (в модели возможно переход будет по последнему обработанному, а на железе неизвестно)
gost_dec.epilogue - несколько условий перехода, которые могут одновременно быть истинными (? уточнить) (в модели возможно переход будет по последнему обработанному, а на железе неизвестно)

Данные условия мы пилили совместно с krufter_multiclet. Это единственный дешёвый способ перейти по нескольким условиям, не прибегая к ещё одному параграфу и повторной перепроверке условий. Условия построены таким образом, чтобы осуществить единственное возможное ветвление.

gost.save_results - новый указатель должен быть ещё на 4 больше

Согласен, надо было сделать ещё один addl @1, 4 перед модификацией BufPtr.

нет сохранения используемых регистров

Это в туду. Работе не мешает — ещё ни разу не видел, чтобы компилятор использовал задействованные мною регистры.

Посмотрел на код. Вся эта магия с or/and/xor ровно для того, чтобы можно было проверить несколько условий в пределах одного параграфа. Ещё три параграфа с кучей кода явно излишне.
Про переходы по #N_P не очень понимаю:
В параграфе gost_dec.epilogue.2 #N_P принимает значение gost_dec.epilogue.3. При выполнении одного из условий мы перейдём в load_keys1_24, подгрузим ключи, а потом перейдём в gost_dec.epilogue.3, где опять повыполняем немного условий и перейдём-таки в gost.round уже без оглядки на #N_P. Как мне кажется, схема ветлвений перестала быть прозрачной, появился оверхед по инструкциям.

Новая модель из SDK 06/Сен падает ещё в crt0:

$ mc-model -inst-asm -inst-strange -dump-raw -dump-addr -dump-byte -dump-symbol -dump-length 4 -dump-from 0x00000000 image.bin
1.0000000000000000 <= 00000000ff9d5c6a, 0000000000000000 :  getl   0x0
0.0000000000000000 <= 0000000000000039, 0000000000000000 :  setl   #MODR(57), @1
0.0000000000000008 <= 0000000000000039, 0000000000000008 :  jmp    0x8
0.0000000000020000 <= 0000000000000039, 0000000000020000 :  getl   0x20000
1.0000000000000000 <= 0000000000000039, 0000000000000000 :  getl   0x0
0.0000000000000004 <= 0000000000000039, 0000000000000004 :  getl   0x4
0.000000000001fffc <= 0000000000020000, 0000000000000004 :  subl   @3, 0x4
0.000000000001fff8 <= 000000000001fffc, 0000000000000004 :  subl   @1, 0x4
Segmentation fault (core dumped)

#0  0x08051c75 in EXECUTION(unsigned long long, unsigned long long*,
          int, int*, unsigned long long*, unsigned long long*, int*, unsigned long long*,
          unsigned long long*, unsigned int*, unsigned int*, int*, int, unsigned long long*) ()
#1  0x08049088 in main ()

ГОСТ в модели выдаёт:

8.00000000b61f9aa0 <= 0000000000000000, 00000000b61f9aa0 :  getl   #1
0.00000000629d1fc2 <= 0000000000000000, 00000000629d1fc2 :  getl   #2

8.00000000ed7e2975 <= 0000000000000000, 00000000ed7e2975 :  getl   #1
8.00000000d48f796f <= 0000000000000000, 00000000d48f796f :  getl   #2

0.000000007afe35fe <= 0000000000000000, 000000007afe35fe :  getl   #1
0.000000001de5ecf9 <= 0000000000000000, 000000001de5ecf9 :  getl   #2

aa=b61f9aa0 bb=629d1fc2
aa=ed7e2975 bb=d48f796f
aa=7afe35fe bb=1de5ecf9

На реальном железе, собранное всё последним SDK так же не работает — encode во второй круг выдаёт: { ECECFDF5, 9AA06670 }, а decode просто вешает.