[Vny4ek 0]

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

принимаю данные с шины и с первого байта приходящего забиваю в буфер

например буфер байт temp[4]={0x72,0x8C,0x23,0x6B};

потом в ходе выполнения программы оказывается нужно еще эти биты использовать но не слева направа формировать из бит байт а справа на лево

например 0х72=01110010b у меня первый байт принятый, а нужно что бы он стал последним, тоесть взять данные и записать их например в другой массив, но использовать биты не слева направо а справа налево тоесть эти биты 0х72=01110010b которые у меня были первыми на самом деле сформировывать должны последний байт и получается 0х9С. Переписывать процедуру приема можно конечно но мне нужно и так и так. Как проще сделать подскажите пожалуста. Пишу на Си для кодвижен

[zltigo 0]

0х72=01110010b ... сформировывать должны .... 0х9С.

Не хилое какое-то преобразование, явно не соответствует написанному.

[aaarrr 63]

Не хилое какое-то преобразование, явно не соответствует написанному.

Еще сдвиг на один бит появился.

[ASN 0]

Vny4ek

тут есть

[Vny4ek 0]

я это вижу как цикл на 8 шагов

где проверяется значение последнего бита в байте и это значение присваивается первому биту новому байту ну и затем сдвиг обоих на 1 вот только знаний не хватает как реализовать

да в пересчете я наврал, ну думаю принцип Вы поняли что я пытался объяснить :)

Изменено 25 апреля, 2010 пользователем Vny4ek

[baralgin 0]

Сумбурное описание, но если правильно понял то типа того:

uint8_t InverseByte(uint8_t b)
{
    uint8_t ret = 0;
    for( int i = 0; i < 8; i++ )
    {
        ret |= ( ( b & ( 1 << i )  ) ? 1 : 0 ) << ( 7 - i );
    }
    return ret;
}

0x72->0x4E

[KRS 0]

IMHO цикл тут неоптимален.

Можно же стандартный способ использовать примерно так он пишется:

a = ((a & 0x55) << 1) | ((a & 0xAA) >> 1);
a = ((a & 0xCC) >> 2) | ((a & 0x33) << 2);
a = (a >> 4) | (a << 4);

[demiurg_spb 0]

Если вопрос звучал так: "Как зеркалить биты в байте?" то самым быстрым способом является таблица из 256 байт (индексом будет исходный байт).

[baralgin 0]

Можно же стандартный способ использовать примерно так он пишется:

a = ((a & 0x55) << 1) | ((a & 0xAA) >> 1);
a = ((a & 0xCC) >> 2) | ((a & 0x33) << 2);
a = (a >> 4) | (a << 4);

Прикольно, наверное Кнут? :)

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

[zltigo 0]

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

То, что Вы написали весьма страшно :(. И дело не в цикле (например стремимся к минимальному размеру, тогда прием KRS отдыхает) а в том, как он написан. Такое:

uint8_t InverseByte(uint8_t b)
{
    uint8_t ret = 0;
    for( uint8_t i = 0x80; i; i >>= 1 )
    {
        if( b & 1 )
             ret |= i;
        b >>= 1;
    }
    return ret;
}

будет в разы короче и быстрее.

 

А такое, чуть увеличившись в размере, если повезет :), обгонит KRS и по скорости:

uint8_t InverseByte(uint8_t b)
{
    uint8_t ret = 0;
    for( uint8_t i = 0x80; b; b >>= 1  )
    {
        if( b & 1 )
             ret |= i;
        i >>= 1;
    }
    return ret;
}

[baralgin 0]

Не поленился, проверил (плохая привычка меряться.. на ночь глядя :) ).

#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <stdint.h>

static uint8_t InverseByte_zltigo(int b )
{
   int ret = 0;
   for( int i = 0x80; i; i >>= 1 )
   {
       if( b & 1 )
            ret |= i;
       b >>= 1;
   }
   return ret;
}

static uint8_t InverseByte_zltigo2(int b )
{
   int ret = 0;
   for( int i = 0x80; b; b >>= 1  )
   {
       if( b & 1 )
            ret |= i;
       i >>= 1;
   }
   return ret;
}

static uint8_t InverseByte(int b )
{
return
(
	(b & 0x01) << 7 |
	(b & 0x02) << 5 |
	(b & 0x04) << 3 |
	(b & 0x08) << 1 |
	(b & 0x10) >> 1 |
	(b & 0x20) >> 3 |
	(b & 0x40) >> 5 |
	(b & 0x80) >> 7
);
}

static void Benchmark( uint8_t (*test_func)(int))
{
   LARGE_INTEGER start, end;
   QueryPerformanceCounter(&start);
int seed = 0x72;
for(int i = 0; i < 100000000; i++ )
    seed = test_func(seed);
   QueryPerformanceCounter(&end);
std::cout << "time=" << end.QuadPart - start.QuadPart << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
Benchmark( &InverseByte_zltigo );
Benchmark( &InverseByte_zltigo2 );
Benchmark( &InverseByte );

return 0;
}

Результат на моём процессоре (A64, Brisbane, L2=512kb):

time=11045076

time=6801262

time=3793456

 

Видимо сравнения мешают. Я внёс немного самодеятельности и обозвал все внутренние переменные int'ом - так быстрее(для всего что выше avr).

 

ps: но по скорости всё равно таблица рулит, как предложили выше.

ps2: мой развёрнутый цикл идёт из немного модифицированного первого варианта: ret |= ( ( b & ( 1 << i ) ) >>i ) << ( 7 - i );

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

Изменено 25 апреля, 2010 пользователем baralgin

[zltigo 0]

Не поленился

Сильно поленились - у Автора всего лишь AVR а не Atlon . А во вторых и для AVR8 это фатально, переврали мои примеры и вписали int вместо insigned char. В третьих, а почему свой вариант не протестировали :)?

Вот как он выглядит на AVR8:

     15          BYTE InverseByte(BYTE b)
   \                     InverseByte:
     16          {
   \   00000000   2F59               MOV     R21, R25
   \   00000002   2F68               MOV     R22, R24
   \   00000004   2F30               MOV     R19, R16
     17              BYTE ret = 0;
   \   00000006   E020               LDI     R18, 0
     18              for( int i = 0; i < 8; i++ )
   \   00000008   E080               LDI     R24, 0
   \   0000000A   E090               LDI     R25, 0
     19              {
     20                  ret |= ( ( b & ( 1 << i )  ) ? 1 : 0 ) << ( 7 - i );
   \                     ??InverseByte_0:
   \   0000000C   2F48               MOV     R20, R24
   \   0000000E   E001               LDI     R16, 1
   \   00000010   E010               LDI     R17, 0
   \   00000012   ....               RCALL   ?S_SHL_L02
   \   00000014   2F13               MOV     R17, R19
   \   00000016   2310               AND     R17, R16
   \   00000018   F011               BREQ    ??InverseByte_1
   \   0000001A   E001               LDI     R16, 1
   \   0000001C   C001               RJMP    ??InverseByte_2
   \                     ??InverseByte_1:
   \   0000001E   E000               LDI     R16, 0
   \                     ??InverseByte_2:
   \   00000020   E010               LDI     R17, 0
   \   00000022   E047               LDI     R20, 7
   \   00000024   1B48               SUB     R20, R24
   \   00000026   ....               RCALL   ?S_SHL_L02
   \   00000028   2B20               OR      R18, R16
     21              }
   \   0000002A   9601               ADIW    R25:R24, 1
   \   0000002C   3088               CPI     R24, 8
   \   0000002E   E000               LDI     R16, 0
   \   00000030   0790               CPC     R25, R16
   \   00000032   F364               BRLT    ??InverseByte_0
     22              return ret;
   \   00000034   2F02               MOV     R16, R18
   \   00000036   2F86               MOV     R24, R22
   \   00000038   2F95               MOV     R25, R21
   \   0000003A   9508               RET
     23          }

А так нормально написанный цикл

     15          BYTE InverseByte(BYTE b)
   \                     InverseByte:
     16          {
     17              BYTE ret = 0;
   \   00000000   E020               LDI     R18, 0
     18              for( BYTE i = 0x80; i; i >>= 1 )
   \   00000002   E810               LDI     R17, 128
     19              {
     20                  if( b & 1 )
   \                     ??InverseByte_0:
   \   00000004   FB00               BST     R16, 0
   \   00000006   F40E               BRTC    ??InverseByte_1
     21                      ret |= i;
   \   00000008   2B21               OR      R18, R17
     22                  b >>= 1;
   \                     ??InverseByte_1:
   \   0000000A   9506               LSR     R16
     23              }
   \   0000000C   9516               LSR     R17
   \   0000000E   F7D1               BRNE    ??InverseByte_0
     24              return( ret );
   \   00000010   2F02               MOV     R16, R18
   \   00000012   9508               RET
     25          }

 

А в четвертых попробуйте этот Ваш сравнительный тест, например, на 0x01 и узнаете немного о везении.

[KRS 0]

ps: но по скорости всё равно таблица рулит, как предложили выше.

Не всегда, все от чипа зависит ;) У некоторых есть инстркуция которая порядок битов меняет.

[baralgin 0]

Сильно поленились - у Автора всего лишь AVR а не Atlon . А во вторых и для AVR8 это фатально, переврали мои примеры и вписали int вместо insigned char. В третьих, а почему свой вариант не протестировали :)? А в четвертых попробуйте этот сравнительный тест, например, на 0x01 и узнаете немного о везении.

Во первых под рукой нет avr и именно по этому uint8_t превратился в int. Для avr конечно нужно просто uint8_t.

Далее свой(первый) вариант протестировал... и он оказался быстрее всех :laughing: - смотрел несколько раз, менял местами тесты. Быстрее он. Видимо архитектура процессора+ компилятор(VS2008Express, оптимизация на скорость).

Насчёт 0x01: не корректно. Потому что компилятор умудряется считать результат до исполнения :) . Зато есть более корректный способ: подать в функцию случайную последовательность. Тогда влияние кэша и предсказателя(и возможно других фишек процессора) будет меньше. Вот новый вариант(с первой функцией) и случайным входом:

#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <stdint.h>

static uint32_t x, y, z, w;
static void reset_xor128()
{
   x = 123456789;
   y = 362436069;
   z = 521288629;
   w = 88675123;
}

static uint32_t xor128()
{
   uint32_t t;
   t=(x^(x<<11));x=y;y=z;z=w;
   return(w=(w^(w>>19))^(t^(t>>8)));
}

static uint8_t InverseByte_zltigo(int b )
{
   int ret = 0;
   for( int i = 0x80; i; i >>= 1 )
   {
       if( b & 1 )
            ret |= i;
       b >>= 1;
   }
   return ret;
}

static uint8_t InverseByte_zltigo2(int b )
{
   int ret = 0;
   for( int i = 0x80; b; b >>= 1  )
   {
       if( b & 1 )
            ret |= i;
       i >>= 1;
   }
   return ret;
}

static uint8_t InverseByte_unroll(int b )
{
return
(
	(b & 0x01) << 7 |
	(b & 0x02) << 5 |
	(b & 0x04) << 3 |
	(b & 0x08) << 1 |
	(b & 0x10) >> 1 |
	(b & 0x20) >> 3 |
	(b & 0x40) >> 5 |
	(b & 0x80) >> 7
);
}

static uint8_t InverseByte_first(int b )
{
   int ret = 0;
   for( int i = 0; i < 8; i++ )
   {
       ret |= ( ( b & ( 1 << i )  ) ? 1 : 0 ) << ( 7 - i );
   }
   return ret;
}

static void Benchmark( uint8_t (*test_func)(int))
{
   LARGE_INTEGER start, end;
reset_xor128();
   QueryPerformanceCounter(&start);
for(int i = 0; i < 100000000; i++ )
    test_func( xor128() & 0xFF );
   QueryPerformanceCounter(&end);
std::cout << "time=" << end.QuadPart - start.QuadPart << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
Benchmark( &InverseByte_unroll );
Benchmark( &InverseByte_first );
Benchmark( &InverseByte_zltigo );
Benchmark( &InverseByte_zltigo2 );

return 0;
}

И результат:

time=4589919

time=4583382

time=18303765

time=16308624

 

ps: После нескольких испытаний пришёл всёже выводу что InverseByte_unroll и InverseByte_first примерно равны по скорости. Но в любом случае это всё архитектурнозависимо и тестировать нужно на том железе, где будет работать(оказывается что даже инструкции специальные для этого бывают :) ).

[Vny4ek 0]

я проще себе это представлял, не знаю только как на языке реализовать:

например

проверяем значение правого бита и присваиваем его левому биту нового байта

далее сдвигаем на 1 в исходном байте вправо (2ой по счету бит справа становится снова 1ым)

также сдвигаем влево на 1 биты в новом байте и повторяем процедуру. так 8 раз