Есть матрица 4х4. в каждой ячейке 0 или 1.
Матрица сохраняется в 16битном регистре по одному биту на ячейку следующим образом (показан № бита, а котором сохраняется значение ячейки)
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Задача — за минимальное число тактов матрицу транспонировать, т.е. получить такую:
0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
Здравствуйте Алексей Петров, Вы писали:
АП>Есть матрица 4х4. в каждой ячейке 0 или 1.
АП>Матрица сохраняется в 16битном регистре по одному биту на ячейку следующим образом (показан № бита, а котором сохраняется значение ячейки)
АП>АП> 0 1 2 3
АП> 4 5 6 7
АП> 8 9 10 11
АП>12 13 14 15
АП>
АП>Задача — за минимальное число тактов матрицу транспонировать, т.е. получить такую:
АП>АП> 0 4 8 12
АП> 1 5 9 13
АП> 2 6 10 14
АП> 3 7 11 15
АП>
si — in, di -out
xor di, di
mov bp, 4
@@1: mov ax, si
mov bx, si
mov cx, si
mov dx, si
ror bx, 3
ror cx, 6
ror dx, 9
and ax, 1
and bx, 2
and cx, 4
and dx, 8
or di, ax
or di, bx
or di, cx
or di, dx
ror si, 1
ror di, 4
dec bp
jnz short @@1
Здравствуйте Алексей Петров, Вы писали:
АП>Есть матрица 4х4. в каждой ячейке 0 или 1.
АП>Матрица сохраняется в 16битном регистре по одному биту на ячейку следующим образом (показан № бита, а котором сохраняется значение ячейки)
АП>АП> 0 1 2 3
АП> 4 5 6 7
АП> 8 9 10 11
АП>12 13 14 15
АП>
АП>Задача — за минимальное число тактов матрицу транспонировать, т.е. получить такую:
АП>АП> 0 4 8 12
АП> 1 5 9 13
АП> 2 6 10 14
АП> 3 7 11 15
АП>
Что-то очень знакомое. Мне про эту задачу рассказывали, что ее как-то давали на каком-то программистском конкурсе.
Самое быстрое решение — это один раз жестко построить таблицу из 65536 вариантов и транспонировать по ней.
Здравствуйте Lexey, Вы писали:
L>Здравствуйте Алексей Петров, Вы писали:
АП>>Есть матрица 4х4. в каждой ячейке 0 или 1.
АП>>Матрица сохраняется в 16битном регистре по одному биту на ячейку следующим образом (показан № бита, а котором сохраняется значение ячейки)
АП>>АП>> 0 1 2 3
АП>> 4 5 6 7
АП>> 8 9 10 11
АП>>12 13 14 15
АП>>
АП>>Задача — за минимальное число тактов матрицу транспонировать, т.е. получить такую:
АП>>АП>> 0 4 8 12
АП>> 1 5 9 13
АП>> 2 6 10 14
АП>> 3 7 11 15
АП>>
L>Что-то очень знакомое. Мне про эту задачу рассказывали, что ее как-то давали на каком-то программистском конкурсе.
L>Самое быстрое решение — это один раз жестко построить таблицу из 65536 вариантов и транспонировать по ней.
Угу. Только на Softool 93, где эта задача выставлялась как конкурсное задание было ограничение на размер в 1 кб.
Здравствуйте Алексей Петров, Вы писали:
Поизвращаюсь я еще на MMX
Пусть строки массива в одну линию будут
align 8
r1_2 dq 0001020304050607h
r3_4 dq 0809101112131415h
tm db 16 dup (0)
TransformMatrix proc r12:QWORD, r34:QWORD
movq MM0, r12
movq MM1, r34
movq MM2, MM0
punpcklbw MM0, MM1
punpckhbw MM2, MM1
movq MM1, MM0
punpcklbw MM0, MM2
punpckhbw MM1, MM2
movq MM2, MM0
psrld MM2, 16
pslld MM0, 16
por MM0, MM2
movq MM2, MM1
psrld MM2, 16
pslld MM1, 16
por MM1, MM2
movq qword ptr [tm], MM1
movq qword ptr [tm+8], MM0
emms
ret
TransformMatrix endp
Вот хороший повод для раздумий. Это я поповоду и той и этой темы.
Это ещё одно хорошее доказательство, что нестолько MMX не столь эффективен при работе с данными меньше байта, а x86 не столь эффективен при переходах. И имено неэфективность переходов, ухудшает код.
Кстати, прошу прощения у модераторов. Однако masquer...
Вот мой email. EdmondXASM@mail.ru свяжись...
Или ICQ 165548002
Может кто поднимит старые наработки с SoftTool-а
