битовые операции

[Valery Ivanov]

Пpивет, All !

1) как "перевернуть" байт ?
те изначально биты расположены 0,1,..7
нужно получить байт с битами 7,6,..0
интересует алгоритм (код на c++)
2) какая на спарках (sparc) структура памяти по отношению к intel
если рассматривать структуры с битовыми полями
3) тот же вопрос если рассматривать сложные структуры где чередуются
обычные данные (double,int) c битовыми полями
в частности как получить адрес битового поля ?
4) url про sparc плз

[ob]

Жму руку тебе, Valery!

01 Aug 06 20:32 --> 01 Aug 06 23:37
Valery Ivanov (2:452/***@FidoNet) --> All

*VI*> 1) как "перевернуть" байт ?
*VI*> те изначально биты расположены 0,1,..7
*VI*> нужно получить байт с битами 7,6,..0
*VI*> интересует алгоритм (код на c++)
*VI*> 2) какая на спарках (sparc) структура памяти по отношению к intel
*VI*> если рассматривать структуры с битовыми полями
*VI*> 3) тот же вопрос если рассматривать сложные структуры где чередуются
*VI*> обычные данные (double,int) c битовыми полями
*VI*> в частности как получить адрес битового поля ?
*VI*> 4) url про sparc плз

Может не надо?.. ;-}

PS1: http://www.sun.com/processors/

LPS: Не стоит принимать близко к сердцу мой бред...

Руку отпускаю, пока. ob.
[*Соседи спят спокойно*]
[_/Necromant's Voice team/_] [*451°F*] [/_Death after Life team_/]
... Мёртвые за углом стоят ...

[Igor Krassikov]

Hello Valery!
19:32 01 Aug 06, Valery Ivanov -> All:

VI> 1) как "перевернуть" байт ?
VI> те изначально биты расположены 0,1,..7
VI> нужно получить байт с битами 7,6,..0
VI> интересует алгоритм (код на c++)

Hапример, так:
unsigned char bitRev(unsigned char x)
{
x = ((x&0x55) << 1) | ((x&0xAA) >> 1);
x = ((x&0x33) << 2) | ((x&0xCC) >> 2);
x = ((x&0x0F) << 4) | ((x&0xF0) >> 4);
return x;
}

Best regards.
Igor

[Igor Krassikov]

Hello Valery!
14:31 02 Aug 06, Igor Krassikov == Valery Ivanov:

Совсем забыл - можно еще и так, например:

unsigned char BitRev(unsigned char x)
{
unsigned int s = (x*0x00020202)&0x01044010;
unsigned int t = (x*0x00080808)&0x02088020;
return (s+t)%4095;
}

Best regards.
Igor

[Stanislav Shwartsman]

Hello Igor!

02 Aug 06 13:39, you wrote to Valery Ivanov:

IK> Совсем забыл - можно еще и так, например:

IK> unsigned char BitRev(unsigned char x)
IK> {
IK> unsigned int s = (x*0x00020202)&0x01044010;
IK> unsigned int t = (x*0x00080808)&0x02088020;
IK> return (s+t)%4095;
IK> }

Ужас. Два умножения, еще и деление.
IMHO первый приз в конкурсе на самую медленную версию :)

Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)

Bye ! [Team Intel Centrino Technology]
Stanislav (AKA Night's Man) [Team Technion]

[Igor Krassikov]

Hello Stanislav!
17:26 02 Aug 06, Stanislav Shwartsman -> Igor Krassikov:

IK>> unsigned char BitRev(unsigned char x)
IK>> {
IK>> unsigned int s = (x*0x00020202)&0x01044010;
IK>> unsigned int t = (x*0x00080808)&0x02088020;
IK>> return (s+t)%4095;
IK>> }

SS> Ужас. Два умножения, еще и деление.
SS> IMHO первый приз в конкурсе на самую медленную версию :)

Интересно, что Уоррен ее приводит как шаг вперед по сравнению с версией со
сдвигами :). Переписывается как

u = x*0x00020202
m = 0x01044010
s = u&m
t = (u<<2)&(m<<1)
x = (0x01001001*(s+t))>>24

так что делений нет, умножений 2. По компактности так точно не уступает первому
варианту :))

Best regards.
Igor

[Stanislav Shwartsman]

Hello Igor!

03 Aug 06 06:36, you wrote to me:

IK> Интересно, что Уоррен ее приводит как шаг вперед по сравнению с
IK> версией со сдвигами :). Переписывается как

IK> u = x*0x00020202
IK> m = 0x01044010
IK> s = u&m
IK> t = (u<<2)&(m<<1)
IK> x = (0x01001001*(s+t))>>24

IK> так что делений нет, умножений 2. По компактности так точно не
IK> уступает первому варианту :))

Это уже звучит лучше, но все равно, вариант с одними сдвигами должен быть
быстрее. Hа современных out-of-order процессорах, чем меньше зависимостей
между инструкциями, тем быстрее будут выполнены вычисления.

А тут мало того, что два умножения (умножение операция не быстрая,
выполняется за несколько тактов), так еще и все от всего зависит, код
абсолютно сериальный.

Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)

Bye ! [Team Intel Centrino Technology]
Stanislav (AKA Night's Man) [Team Technion]

[Igor Krassikov]

Hello Stanislav!
11:45 03 Aug 06, Stanislav Shwartsman -> Igor Krassikov:

SS> Это уже звучит лучше, но все равно, вариант с одними сдвигами должен быть
SS> быстрее. Hа современных out-of-order процессорах, чем меньше зависимостей
SS> между инструкциями, тем быстрее будут выполнены вычисления.
SS> А тут мало того, что два умножения (умножение операция не быстрая,
SS> выполняется за несколько тактов), так еще и все от всего зависит, код
SS> абсолютно сериальный.

Скорее наоборот... А во втором варианте как минимум s и t вычисляются
отдельно. Впрочем "к чему слова, зачем так много треска?" (с) :-)) Практика,
как известно, критерий истины...

#include <stdio.h>

unsigned char br(unsigned char x)
{
x = ((x&0x55) << 1) | ((x&0xAA) >> 1);
x = ((x&0x33) << 2) | ((x&0xCC) >> 2);
x = ((x&0x0F) << 4) | ((x&0xF0) >> 4);
return x;
}

unsigned char BR(unsigned char x)
{
unsigned int u = x*0x00020202;
const unsigned int m = 0x01044010, n = 0x2088020;
unsigned int s = u&m;
unsigned int t = (u<<2)&n;
return (0x01001001*(s+t))>>24;
}

void main()
{

long long start = muTime();
for(int i = 0; i < 100000; ++i)
{
for(unsigned int x = 0; x <=0xFE; ++x)
{
unsigned char z = br(x);
}
}
long long stop = muTime();
printf("Time: %ld mks\n",stop-start);
start = muTime();
for(int i = 0; i < 100000; ++i)
{
for(unsigned int x = 0; x <=0xFE; ++x)
{
unsigned char z = BR(x);
}
}
stop = muTime();
printf("Time: %ld mks\n",stop-start);
}

muTime() - моя функция, которая под OS/2 честно меряет время с точностью до
микросекунд.
Open Watcom 1.5, wcl386 -otx.

Hачнем с того, что код br - 74 байта, код BR - 54 байта. Время соответственно -
0.249 и 0.175 секунд (Celeron IV).

Best regards.
Igor

[Valery Ivanov]

Пpивет, Igor !

IK> Совсем забыл - можно еще и так, например:

unsigned char BitRev(unsigned char x)
{
unsigned int s = (x*0x00020202)&0x01044010;
unsigned int t = (x*0x00080808)&0x02088020;
return (s+t)%4095;
}

IK> unsigned char BitRev(unsigned char x)
IK> {
IK> unsigned int s = (x*0x00020202)&0x01044010;

0x00020202= a0 = 2^1 + 2^9 + 2^17
0x01044010 = b0 = 2^4 + 2^14 + 2^18 + 2^24

0x00080808= a1 = 4*a0
0x02088020= b1 = 2*b0
наш x = (x7,...,x0)

рассмотрим число xk= x*2^k = x<<k = (x7,...,x0, 0,...0)
тогда выражение k
(x*2^k)&2^m = xk[m]*2^m = x[m-k]*2^m, 7 => m-k >=0
= 0, (m-k)<0 || (m-k)>7

тогда составив табличку получим
s = (x*a0)&b0 = (x*(2^1 + 2^9 + 2^17)) & (2^4 + 2^14 + 2^18 + 2^24)
= x[2]*2^5 + x[4]*2^15 + x[0]*2^19 + x[6]*2^25

t =(x*a1)&b1 = x[3]*2^4 + x[5]*2^14 + x[1]*2^18 + x[7]*2^24

IK> unsigned int t = (x*0x00080808)&0x02088020;

4095 = 2^12 - 1
s+t = 2^12*A0+B0 = (2^12-1)*A0+A0 +B0
где
A0 = x[5]*2^2 + x[1]*2^6 + x[7]*2^12 + x[4]*2^3 + x0*2^7 + x6*2^13
B0 = x[3]*2^4 + x[2]*2^5

A0 = 2^12*A1 + B1 = (2^12-1)*A1 + A1 + B1
A1 = x[7]*2^0 + x[6]*2^1
B1 = x[5]*2^2 + x[1]*2^6+x[4]*2^3 + x[0]*2^7

IK> return (s+t)%4095;

(s+t)%4095 = B0 + A1+B1 = x[3]*2^4 + x[2]*2^5 + x[7]*2^0 + x[6]*2^1
+ x[5]*2^2 + x[1]*2^6 + x[4]*2^3 + x[0]*2^7

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

IK> }

[Igor Krassikov]

Hello Valery!
20:58 07 Aug 06, Valery Ivanov -> Igor Krassikov:
VI> видно что байт переставлен

При всем уважении к теории :) замечу, что для байта (8 бит, 256 вариантов)
проще проверить практически, набросав за 5 минут соответствующую программку.
Еще раз оговорюсь - для нашего случая - 8 бит.

Best regards.
Igor

[Valery Ivanov]

Пpивет, Igor !

VI>> 1) как "перевернуть" байт ?
VI>> те изначально биты расположены 0,1,..7
VI>> нужно получить байт с битами 7,6,..0
VI>> интересует алгоритм (код на c++)

IK> Hапример, так:
IK> unsigned char bitRev(unsigned char x)
IK> {

01234567

IK> x = ((x&0x55) << 1) | ((x&0xAA) >> 1);

перестановка1
1010101 55
10101010 AA
10325476

IK> x = ((x&0x33) << 2) | ((x&0xCC) >> 2);

перестановка2
110011 33
11001100 CC
32107654

IK> x = ((x&0x0F) << 4) | ((x&0xF0) >> 4);



перестановка3
0F 1111
F0 11110000
76543210

IK> return x;

все верно

IK> }

математическое обьяснение :
перестановка = перестановка3*перестановка2*перестановка1
в самом деле
перестановка3 : i -> (i-4) mod 8
перестановка2 : i -> i1= (i-2) mod 4 если рассматривать внутренний
набор в 4 бита и в общем - i -> i1 + ( i div 4) * 4
перестановка1: i -> i2 = (i-1) mod 2 если рассматривать
внутренний набор и в общем i -> i2 + (i div 2)*2
теперь считаем:
1: i-> (i-1) mod 2 + (i div 2)* 2 = i_1
2: i_1 -> (i_1-2) mod 4 + (i_1 div 4)*4 = i_2
3: i_2 -> (i_2 - 4) mod 8 = i_3
подсчитав получаем i_3 = 7-i
действительно представим индекс i = 2^2*i2+2*i1+1*i0 = (i2,i1,i0) в двоичной
системе
тогда перестановка 1:
i div 2 = 2*i2+i1
(i-1) mod 2 = (i0-1) mod 2 = (1-i0)
те i=(i2,i1,i0) -> 2*(2*i2+i1)+(1-i0) = 4*i2 + 2*i1 + (1-i0) -> (i2,i1,1-i0)
перестановка 2:
i div 4 = i2
(i-2) mod 4 = (2*(i1-1) + 1*i0) mod 4 = 2*(1-i1)+i0
те i = (i2,i1,i0) -> 4 * (i2) + 2* (1 -i1) + i0 -> (i2,1-i1,i0)
перестановка3
i -> (i-4) mod 8 = (4*(i2-1)+2*i1+1*i0) mod 8 = 4*(1-i2)+2*i1+1*i0 ->
(1-i2,i1,i0)
комбинация перестановок даст нам i = (i2,i1,i0) -> (1-i2,1-i1,1-i0) = 7-i

ps это я просто прокомментировал

кстати, при разборе можно попробовать воспользоваться
1) средствами мат логики
тогда последняя строка например расшифруется так
((x&0x0F)<<4)| ((x&0xF0)>>4) = ((x<<4)&0xF0)|(x>>4)&0x0F)=
= (x<<4)|(x>>4)
2) средствами чистой математики
вспомним что x mod k = k*{x/k} , {x} - дробная часть x
x div k = [x/k] [x] - целая часть x, x = {x}+[x],
0<={x}<1
тогда например перестановка 1 разберется так :

(i-1) mod 2 + 2* (i div 2) =
{(i-1)/2}*2 + 2* ( [i/2] )=
(i-1) + 2* ( [i/2]-[(i-1)/2])

но [i/2] - [(i-1)/2] = 1 , i - четное, = 0 , i - нечетное
следовательно
перестановка1 : i -> i+1 , i- четное,
i-1, i- нечетное

[Kirill Frolov]

Post by Valery Ivanov
1) как "перевернуть" байт ?
те изначально биты расположены 0,1,..7
нужно получить байт с битами 7,6,..0
интересует алгоритм (код на c++)

Сдвиг влево в флаг переноса, сдвиг вправо из флага переноса. И так 8
раз подряд. C-два-креста тут не помогут. Табличным методом -- не
спортивно.

Post by Valery Ivanov
3) тот же вопрос если рассматривать сложные структуры где чередуются
обычные данные (double,int) c битовыми полями
в частности как получить адрес битового поля ?

А в эём этот адрес считать? В каких единицах?

[Evgenij Masherov]

Tue Aug 01 2006 20:32, Valery Ivanov wrote to All:


VI> 1) как "перевернуть" байт ?
VI> те изначально биты расположены 0,1,..7
VI> нужно получить байт с битами 7,6,..0
VI> интересует алгоритм (код на c++)

Сделать таблицу в 256 элементов. И выбирать.

Евгений Машеров АКА СанитарЖеня

[Valery Ivanov]

Пpивет, Evgenij !

VI>> 1) как "перевернуть" байт ?
VI>> те изначально биты расположены 0,1,..7
VI>> нужно получить байт с битами 7,6,..0
VI>> интересует алгоритм (код на c++)

EM> Сделать таблицу в 256 элементов. И выбирать.

если честно то я давным давно уже написал две функции
переворачивания байта
одна - честно работает по битам
вторая - реализована через union и структуры в которых
перевернуто расположения полей
но ты просто уже третий или четвертый чел, который написал что нужна
таблица
детский вопрос : на кой черт эта таблица ?
или я чего то не догоняю ?

[Miguel Mitrofanov]

Hello, Valery! You wrote:

VI>>> 1) как "перевернуть" байт ?
VI> но ты просто уже третий или четвертый чел, который написал что
VI> нужна таблица детский вопрос : на кой черт эта таблица ? или я
VI> чего то не догоняю ?

Ну дык самый простой способ

byte reverse(b:byte){return table[b];}

Правда, самый простой не значит самый быстрый; всё-таки обращение к
памяти... С другой стороны, при частом использовании таблица имеет все
шансы закэшироваться.

[Evgenij Masherov]

Sat Aug 05 2006 23:22, Valery Ivanov wrote to Evgenij Masherov:


VI>>> 1) как "перевернуть" байт ?
VI>>> те изначально биты расположены 0,1,..7
VI>>> нужно получить байт с битами 7,6,..0
VI>>> интересует алгоритм (код на c++)

EM>> Сделать таблицу в 256 элементов. И выбирать.

VI> если честно то я давным давно уже написал две функции
VI> переворачивания байта
VI> одна - честно работает по битам
VI> вторая - реализована через union и структуры в которых
VI> перевернуто расположения полей
VI> но ты просто уже третий или четвертый чел, который написал что нужна
VI> таблица
VI> детский вопрос : на кой черт эта таблица ?
VI> или я чего то не догоняю ?

Для "переворачивания" в одну операцию...
Hасколько эффективно - зависит от конкретной машины.

Евгений Машеров АКА СанитарЖеня

[Stanislav Shwartsman]

Hello Valery!

05 Aug 06 23:22, you wrote to Evgenij Masherov:

VI>>> 1) как "перевернуть" байт ?
VI>>> те изначально биты расположены 0,1,..7
VI>>> нужно получить байт с битами 7,6,..0
VI>>> интересует алгоритм (код на c++)

EM>> Сделать таблицу в 256 элементов. И выбирать.

VI> если честно то я давным давно уже написал две функции
VI> переворачивания байта
VI> одна - честно работает по битам
VI> вторая - реализована через union и структуры в которых
VI> перевернуто расположения полей
VI> но ты просто уже третий или четвертый чел, который написал что нужна
VI> таблица
VI> детский вопрос : на кой черт эта таблица ?
VI> или я чего то не догоняю ?

Потому что сделать переворот быстрее и проще, чем коммандой

a = table[b]

очень и очень сложно.

Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)

Bye ! [Team Intel Centrino Technology]
Stanislav (AKA Night's Man) [Team Technion]

[Michael Mamaev]

Хоpошее Кино это вино. Выпьем, Valery?
Сyббота Авгyст 05 2006 23:22, Valery Ivanov wrote to Evgenij Masherov:

VI> но ты пpосто yже тpетий или четвеpтый чел, котоpый написал что нyжна
VI> таблица
VI> детский вопpос : на кой чеpт эта таблица ?
VI> или я чего то не догоняю ?

Hе догоняешь :)
Все зависит от того, насколько тебя жмёт по памяти и по скоpости. В некотоpых
аpхитектypах, где сиё действо тpебyется пpовоpачивать часто и быстpо, вообще
сyществyет специальная команда пpоцессоpа, котоpая делает все за один такт.

А если не жмёт - делай как полyчится, делов-то.


Майкл