Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Матрица 8х8 - как заменить столбцы строками ?
Форум разработчиков электроники ELECTRONIX.ru > Микроконтроллеры (MCs) > AVR
french
Реальная задача для контроллера Мega128 (CVAVR):
есть две матрицы 8х8 бит - два массива по 8 байт
Код
// здесь какждый байт массива представляет собой столбец матрицы
char Vbuf[1][8] = {... типа данные};
// а этом случае каждый байт массива - это строка
char Hbuf[8][1] = {... типа данные};

в общем данные хранятся примерно так ...
Vbuf[1][8];                 Hbuf[8][1];

0  0  0  0  0  0  0  0     0 1 2 3 4 5 6 7
1  1  1  1  1  1  1  1     0 1 2 3 4 5 6 7
2  2  2  2  2  2  2  2     0 1 2 3 4 5 6 7
3  3  3  3  3  3  3  3     0 1 2 3 4 5 6 7
4  4  4  4  4  4  4  4     0 1 2 3 4 5 6 7
5  5  5  5  5  5  5  5     0 1 2 3 4 5 6 7
6  6  6  6  6  6  6  6     0 1 2 3 4 5 6 7
7  7  7  7  7  7  7  7     0 1 2 3 4 5 6 7

т.е. первый байт Vbuf представляет собой  0-ые биты каждого байта Hbuf
второй байт Vbuf представляет собой 1-ые биты каждого байта Hbuf и т.д....

Требуется преобразовать матрицу Vbuf в Hbuf.

Простейшее решение - побитовое копирование.
В это случае контроллер должен будет сделать (8х8)*(команды извлечения бита + команды копирования бита + куча команд для формиро циклов) операций. В итоге получается АЦКАЯ работа.
В моем случае таких матриц к примеру 80 и обработка занимает порядка 50мс.

Хотелось бы услышать дельные советы бывалых программеров о том как оптимизировать алгоритм (мега тактируестя 20МГц и менять ее на что-то более мощное не возможности). Может стоит по другому организовать хранение данных или есть типовые алгоритмы. Буду рад услышать любой совет !!!!
Rst7
Алгоритм то есть. Не факт, правда, что на AVR он будет быстрее чем копирование битов, хотя можно попробовать. Готового исходника у меня под рукой нет, но основную идею постараюсь обрисовать.

Есть 8 байт, сперва необходимо провернуть по биту
Код
76543210 - 1й байт
HGFEDCBA - 2й байт
76543210 - 3й байт
HGFEDCBA - 4й байт
76543210 - 5й байт
HGFEDCBA - 6й байт
76543210 - 7й байт
HGFEDCBA - 8й байт

нужно изготовить
Код
6G4E2C0A
7H5F3D1B
6G4E2C0A
7H5F3D1B
6G4E2C0A
7H5F3D1B
6G4E2C0A
7H5F3D1B


Следующая стадия - проворот по 2 бита, следующая - по четыре.
Обрисую результат стадии поворота по 2 бита (участвуют по 4 байта), одна цифра - 2 бита:
Код
3210
7654
DCBA
HGFE

->
Код
2C0A
6G4E
3D1B
7H5F


и последний поворот по 4 бита
Код
10
32

->
Код
02
13
vet
а цель какова? может, оно и не нужно вовсе, такое вот преобразование?
=GM=
Цитата(french @ Mar 10 2008, 12:36) *
Реальная задача для контроллера Мega128 (CVAVR): есть две матрицы 8х8 бит - два массива по 8 байт
...
т.е. первый байт Vbuf представляет собой 0-ые биты каждого байта Hbuf, второй байт Vbuf представляет собой 1-ые биты каждого байта Hbuf и т.д. Требуется преобразовать матрицу Vbuf в Hbuf.

Простейшее решение - побитовое копирование.
В это случае контроллер должен будет сделать (8х8)*(команды извлечения бита + команды копирования бита + куча команд для формиро циклов) операций. В итоге получается АЦКАЯ работа.
В моем случае таких матриц к примеру 80 и обработка занимает порядка 50мс.

Хотелось бы услышать дельные советы бывалых программеров о том как оптимизировать алгоритм (мега тактируестя 20МГц и менять ее на что-то более мощное нет возможности). Может стоит по другому организовать хранение данных или есть типовые алгоритмы. Буду рад услышать любой совет !!!!

Разместите 8 байт вашего Vbuf в регистрах r0-r7 и делайте побитное копирование, например, вызывая такую подпрограмму:
Код
getHbyte:
   ror   r0
   ror   r8
   ror   r1
   ror   r8
   ror   r2
   ror   r8
   ror   r3
   ror   r8
   ror   r4
   ror   r8
   ror   r5
   ror   r8
   ror   r6
   ror   r8
   ror   r7
   ror   r8  ;готов n-й байт Hbuf
   ret
забираете готовый байт и повторяете ещё 7 раз. На один байт уйдёт 23МЦ, на одну конвертацию вгрубе уйдёт всего 8*23*0.05=9.2 мкс, на 80 уйдёт 80*9.2=736 мкс, откуда 50 мс?
SasaVitebsk
А зачем её поворачивать вообще?

При обращении к одной - используйте координаты X,Y, а для другой Y,X.
kv_addr
Транспонирование матрицы битов:
Код
   b0 b1 b2 b3 b4 b5 b6 b7      b0 b1 b2 b3 b4 b5 b6 b7
r0 00 01 02 03 04 05 06 07  r8  00 10 20 30 40 50 60 70
r1 10 11 12 13 14 15 16 17  r9  01 11 21 31 41 51 60 71
r2 20 21 22 23 24 25 26 27  r10 02 12 22 32 42 52 62 72
r3 30 31 32 33 34 35 36 37  r11 03 13 23 33 43 53 63 73
r4 40 41 42 43 44 45 46 47  r12 04 14 24 34 44 54 64 74
r5 50 51 52 53 54 55 56 57  r13 05 15 25 35 45 55 65 75
r6 60 61 62 63 64 65 66 67  r14 06 16 26 36 46 56 66 76
r7 70 71 72 73 74 75 76 77  r15 07 17 27 37 47 57 67 77

Простой вариант "в лоб".
Исходная помещается в r0-r7, результирующая получается в r8-r15:
Код
    movw r8,r0
    mowv r10,r2
    movw r12,r4
    movw r14,r6
    bst r0,1
    bld r9,0  // из 01 перенесено в 10 другой матрицы
    bst r1,0
    bld r8,1  // из 10 перенесено в 01 другой матрицы
    ...
    bst r6,7
    bld r15,6 // из 67 перенесено в 76 другой матрицы
    bst r7,6
    bld r14,7 // из 76 перенесено в 67 другой матрицы

Всего необходимо 28 взаимных пересылок, что в результате занимает 28х4=112 тактов. Плюс 4 такта копирования регистровых пар, получается 116 тактов. Итого транспонирование матрицы битов занимает по времени 5,8 мкс. Для 80 матриц - 464 мкс, с накладыми расходами пусть будет ~0,5 мс, т.е. в 100 раз быстрее, чем у Вас получилось.

PS: Сейчас не вспомню, но существует более быстый способ транспонирования, дающий экономию еще около 20% времени.
vetal
Цитата
А зачем её поворачивать вообще?

При обращении к одной - используйте координаты X,Y, а для другой Y,X.

+1 smile.gif
Код
char buf[8][8] = {... типа данные};
#define Vbuf(x,y) buf[x][y]
#define Hbuf(x,y) buf[y][x]
kv_addr
Цитата(vetal @ Mar 11 2008, 01:39) *
+1 smile.gif
Код
char buf[8][8] = {... типа данные};
#define Vbuf(x,y) buf[x][y]
#define Hbuf(x,y) buf[y][x]

sad.gif По условию задачи было не 8х8 байт, а 8х8 бит. Вроде так. 07.gif
Непомнящий Евгений
таблицу соответствия можно использовать - будет быстро, но надо 256 байт памяти.
Rst7
Цитата
таблицу соответствия можно использовать - будет быстро, но надо 256 байт памяти.


Это простите как? Что хранить в этой таблице?
Непомнящий Евгений
Цитата(Rst7 @ Mar 11 2008, 10:34) *
Это простите как? Что хранить в этой таблице?

Упс, поспешил. Этот вариант не подходит.
Rst7
Цитата
Упс, поспешил. Этот вариант не подходит.


Именно. Видимо, для AVR оптимальный вариант - развернутое копирование битов, варианты со сдвигами хороши для большей разрядности, например 32.
Непомнящий Евгений
А вариант
Код
#define TESTBIT(v, n) ( (v>>n) & 1)
char buf[8] = {... типа данные};
#define Vbuf(x,y) TESTBIT(buf[x], y)
#define Hbuf(x,y) TESTBIT(buf[y], x)

чем не устраивает?
french
Правильно задать вопрос - пол проблемы решить !!! Чтобы не путать уважаемою аудиторию постараюсь яснее изложить мою проблему:
Есть два массива по 8 байт (а в реале размер кратен 8)
unsigned char Vbuf[8];
unsigned char Hbuf[8];

пусть Vbuf будет таким:

12345678 - 1-й байт
ABCDEFGH - 2-й байт
87654321 - 3-й байт
abcdefgh - 4-й байт
QWERTYUI - 5-й байт
qwertyui - 6-й байт
ASDFGHJK - 7-й байт
asdfghjk - 8-й байт

надо скопировать в Hbuf так чтобы в нем
1A8aQqAa - 1-й байт
2B7bWwSs - 2-й байт
3C6cEeDd - 3-й байт
4D5dRrFf - 4-й байт
5e4eTtGg - 5-й байт
6F3fYyHh - 6-й байт
7G2gUuJj - 7-й байт
8H1hIiKk - 8-й байт

решение задачи в лоб (побитовое копирование) выглядит так:
Код
#define _HEIGHT 16    // высота экрана в строках (битах)
#define _WIDTH     4    // ширина экрана кратная 1 байту
#define _H _HEIGHT/8
#define _W _WIDTH*8

unsigned char SCREEN2[_HEIGHT][_WIDTH];    // буфер видео-памяти (G-формат)
unsigned char BUFFER [_H][_W];            // рабочий буфер видео-памяти (V-формат)
unsigned char ws_i=0, wb_i=0, hsi_bit=0, hs_i=0, hs_byte=0;
// преобразование данных из вертикального формата
// в горизонталный
for(ws_i=0; ws_i<_WIDTH; ws_i++)
{
    for(hs_i=0; hs_i<_HEIGHT; hs_i++)
    {
        if(hsi_bit > 7)    {hsi_bit=0;  hs_byte++;}
        for(wb_i=0; wb_i<8; wb_i++)
               SCREEN[hs_i][ws_i] |= (((unsigned char)BUFFER[hs_byte][(unsigned int)(wb_i+ 8*ws_i)]>>hsi_bit)<<7)>>wb_i; // собственно побитовое копирование !!!

            hsi_bit++;
     }
     hs_byte=0;
     hsi_bit=0;
}

эта штука работает, но долго !!!

Цитата
Простой вариант "в лоб".
Исходная помещается в r0-r7, результирующая получается в r8-r15:
movw r8,r0
mowv r10,r2
movw r12,r4
movw r14,r6
bst r0,1
bld r9,0 // из 01 перенесено в 10 другой матрицы
bst r1,0
bld r8,1 // из 10 перенесено в 01 другой матрицы
...
bst r6,7
bld r15,6 // из 67 перенесено в 76 другой матрицы
bst r7,6
bld r14,7 // из 76 перенесено в 67 другой матрицы

Всего необходимо 28 взаимных пересылок, что в результате занимает 28х4=112 тактов. Плюс 4 такта копирования регистровых пар, получается 116 тактов. Итого транспонирование матрицы битов занимает по времени 5,8 мкс. Для 80 матриц - 464 мкс, с накладыми расходами пусть будет ~0,5 мс, т.е. в 100 раз быстрее, чем у Вас получилось.

класс, но пишу на Си, регистры все заняты компилятором !!! можно конечно сохранять их значения а потом восстанавливать, но 16 регистров.... помоему не реально.
Rst7
Цитата
но пишу на Си, регистры все заняты компилятором !!!


Напишите именно эту процедуру на ассемблере.


Кстати, а зачем это делать в динамике? Это же шрифт, как я понимаю? Почему бы его не развернуть заранее?
kv_addr
Цитата(french @ Mar 11 2008, 13:13) *
класс, но пишу на Си, регистры все заняты компилятором !!! можно конечно сохранять их значения а потом восстанавливать, но 16 регистров.... помоему не реально.

Наболее быстрые операции - регистровые. Поэтому для быстрого транспонирования матрицы хорошей альтернативы им нет. Не вижу принципиальной невозможности для выделения 16 регистров, хотя при некотором снижении скорости можно обойтись и 8+1=9 регистрами. Тут возможны варианты реализации, попробуйте найти самостоятельно (Hint: 9-й нужен для временного хранения старых значений битов одного из регистров матрицы). В принципе достаточно было бы и 8 регистров, если бы был еще один флаг T. wink.gif
french
Цитата
Напишите именно эту процедуру на ассемблере.
Кстати, а зачем это делать в динамике? Это же шрифт, как я понимаю? Почему бы его не развернуть заранее?

Это действительно шрифт. Текст может быть известен только во время выполнения программы (напр. время, температура, и т.д.). А склеивать символы или делать различные эффекты проще когда байты расположены вертикально.
Rst7
Ну и зачем его хранить в горизонтальном виде? Храните сразу в вертикальном, не вижу проблем.
french
в том то и фикус smile.gif , что я все делаю в вертикальном виде, на устройство можно выводить тока в горизонтальном !!!!
Rst7
Так делайте в горизонтальном, не сильно то много разницы. Особенно с учетом того, что аппаратное умножение отлично заменяет сдвиг - это если надо с точностью до пиксела символы выводить, а не с точностью до байта.

А вообще, было бы неплохо огласить, че за устройство. Или опять бегущая строка?
french
Цитата
А вообще, было бы неплохо огласить, че за устройство. Или опять бегущая строка?

Она родная !!! А если проблему разбить по частям. Как максимально быстро скопировать бит. Моя способ я понимаю не идеал:
Код
SCREEN |= ((BUFFER>>hsi_bit)<<7)>>wb_i;
Rst7
Цитата
Как максимально быстро скопировать бит. Моя способ я понимаю не идеал:


А зачем копировать бит? Надо копировать одну строку символа, а не бит. Для этого самый раз пользоваться умножением для сдвига на нужное количество бит - умножая на 2^n и получая int из char, а этот int потом делаем or с буфером экрана.
singlskv
Цитата(Rst7 @ Mar 11 2008, 10:59) *
....., варианты со сдвигами хороши для большей разрядности, например 32.
Неа, судя по всему сдвиги будут рулить и на AVR, все почему то дружно
забыли что команды rol/ror двигают сразу 2 бита (один задвигает, один выдвигает),
это в 2 раза эфективнее чем просто копирование битов,.....
Rst7
Цитата
Неа, судя по всему сдвиги будут рулить и на AVR,


Я имел в виду транспонирование по алгоритму, который я в начале треда описал. А насчет выдвигания-задвигания надо конечно подумать, но мне кажется, что толку не будет...
CDT
Что - то трудно понимаемое.
Вы на выходной порт всю матрицу сразу посылаете? А скорость сканирования несколько мегагерц?

Сформируйте конкретный байт перед выдачей на внешний порт.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.