реклама на сайте
подробности

 
 
> Матрица 8х8 - как заменить столбцы строками ?, требуется БЫСТРЫЙ алгоритм обработки
french
сообщение Mar 10 2008, 12:36
Сообщение #1


Участник
*

Группа: Участник
Сообщений: 34
Регистрация: 21-09-04
Пользователь №: 688



Реальная задача для контроллера М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МГц и менять ее на что-то более мощное не возможности). Может стоит по другому организовать хранение данных или есть типовые алгоритмы. Буду рад услышать любой совет !!!!
Go to the top of the page
 
+Quote Post
 
Start new topic
Ответов
french
сообщение Mar 11 2008, 09:13
Сообщение #2


Участник
*

Группа: Участник
Сообщений: 34
Регистрация: 21-09-04
Пользователь №: 688



Правильно задать вопрос - пол проблемы решить !!! Чтобы не путать уважаемою аудиторию постараюсь яснее изложить мою проблему:
Есть два массива по 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 регистров.... помоему не реально.
Go to the top of the page
 
+Quote Post

Сообщений в этой теме
- french   Матрица 8х8 - как заменить столбцы строками ?   Mar 10 2008, 12:36
- - Rst7   Алгоритм то есть. Не факт, правда, что на AVR он б...   Mar 10 2008, 13:01
- - vet   а цель какова? может, оно и не нужно вовсе, такое ...   Mar 10 2008, 13:03
- - =GM=   Цитата(french @ Mar 10 2008, 12:36) Реаль...   Mar 10 2008, 14:35
- - SasaVitebsk   А зачем её поворачивать вообще? При обращении к о...   Mar 10 2008, 20:46
- - kv_addr   Транспонирование матрицы битов: Код b0 b1 b2 b3 ...   Mar 10 2008, 21:02
- - vetal   ЦитатаА зачем её поворачивать вообще? При обращен...   Mar 10 2008, 21:39
|- - kv_addr   Цитата(vetal @ Mar 11 2008, 01:39) +1 Ко...   Mar 10 2008, 22:26
- - Непомнящий Евгений   таблицу соответствия можно использовать - будет бы...   Mar 11 2008, 07:31
- - Rst7   Цитататаблицу соответствия можно использовать - бу...   Mar 11 2008, 07:34
|- - Непомнящий Евгений   Цитата(Rst7 @ Mar 11 2008, 10:34) Это про...   Mar 11 2008, 07:51
- - Rst7   ЦитатаУпс, поспешил. Этот вариант не подходит. Им...   Mar 11 2008, 07:59
|- - singlskv   Цитата(Rst7 @ Mar 11 2008, 10:59) ....., ...   Mar 11 2008, 20:32
- - Непомнящий Евгений   А вариант Код#define TESTBIT(v, n) ( ...   Mar 11 2008, 08:13
|- - kv_addr   Цитата(french @ Mar 11 2008, 13:13) класс...   Mar 11 2008, 10:11
- - Rst7   Цитатано пишу на Си, регистры все заняты компилято...   Mar 11 2008, 10:11
- - french   ЦитатаНапишите именно эту процедуру на ассемблере....   Mar 11 2008, 10:34
- - Rst7   Ну и зачем его хранить в горизонтальном виде? Хран...   Mar 11 2008, 10:38
- - french   в том то и фикус , что я все делаю в вертикальном...   Mar 11 2008, 10:43
- - Rst7   Так делайте в горизонтальном, не сильно то много р...   Mar 11 2008, 10:49
- - french   ЦитатаА вообще, было бы неплохо огласить, че за ус...   Mar 11 2008, 12:02
- - Rst7   ЦитатаКак максимально быстро скопировать бит. Моя...   Mar 11 2008, 12:48
- - Rst7   ЦитатаНеа, судя по всему сдвиги будут рулить и на ...   Mar 12 2008, 06:13
- - CDT   Что - то трудно понимаемое. Вы на выходной порт вс...   Mar 14 2008, 12:11


Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 20th July 2025 - 20:00
Рейтинг@Mail.ru


Страница сгенерированна за 0.01366 секунд с 7
ELECTRONIX ©2004-2016