Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит / 25 сообщений из 104, страница 1 из 5
27.11.2020, 09:52
    #40022657
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Дано: 2 Word-а по 16 бит :)
Необходимо объединить их так, чтобы биты шли последовательно
Можно ли сделать это без многочисленных умножений или огромных заранее рассчитанных таблиц?

Пример:

0101010101010101 op 1100111000111100 = 0111001001110110111001110010
...
Рейтинг: 0 / 0
27.11.2020, 10:00
    #40022663
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
О, в моём примере не так
Но важное уточнение

На практике не бывает, что оба n-ных бита равны 1
Может быть пригодится
...
Рейтинг: 0 / 0
27.11.2020, 10:40
    #40022674
bk0010
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
makewparam(lo,hi),
makelong(lo,hi),
LongRec(MyIntVariable).Lo := ..., LongRec(MyIntVariable).Hi := ...,
MyIntVariable:= Lo + Hi shl 16; ?
...
Рейтинг: 0 / 0
27.11.2020, 10:51
    #40022678
alekcvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Ошибся.
...
Рейтинг: 0 / 0
27.11.2020, 11:03
    #40022681
alekcvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU,

Ну у меня как-то так получилось в блокнотике:
Код: pascal
1.
2.
3.
4.
5.
6.
Result := 0; // DWORD;
for var i := 15 downto 0 do
begin
  Mask := 1 shl i; // Word
  Result := Result shl 1 or DWORD(WordA and Mask) shl 1 or DWORD(WordB and Mask);
end;
...
Рейтинг: 0 / 0
27.11.2020, 14:02
    #40022767
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU
Дано: 2 Word-а по 16 бит :)
Необходимо объединить их так, чтобы биты шли последовательно
Можно ли сделать это без многочисленных умножений или огромных заранее рассчитанных таблиц?

Пример:

0101010101010101 op 1100111000111100 = 0111001001110110111001110010


Ассемблер подойдет?
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
function Mix( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    ESI
     Push    EDI
     Push    EBX

     Xor     ESI,    ESI    // обнуляем временный результат
     Mov     EDI,    01h    // маска установки единичных битов w1 и w2

     Mov     ECX,    0Fh    // количество итераций
     Mov     EBX,    01h    // текущий сравниваемый бит для w1 и w2

@@10:
     Test    EAX,    EBX    // проверяем текущий бит для w1
     Jz      @@20

     Or      ESI,    EDI    // устанавливаем единичный бит w1

@@20:
     Shl     EDI,    01h    // сдвигаем текущий бит для w2
     Test    EDX,    EBX    // проверяем текущий бит для w2
     Jz      @@30

     Or      ESI,    EDI    // устанавливаем единичный бит w2

@@30:
     Shl     EDI,    01h    // сдвигаем текущий бит для w1
     Shl     EBX,    01h    // сдвигаем общий проверяемый бит
     Loop    @@10

     Mov     EAX,    ESI    // присваиваем временный результат

     Pop     EBX
     Pop     EDI
     Pop     ESI
end;
...
Рейтинг: 0 / 0
27.11.2020, 17:02
    #40022828
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Я честно говоря думал есть способ обойтись парой умножений и битовыми операциями
В общем спасибо за участие!
...
Рейтинг: 0 / 0
27.11.2020, 17:04
    #40022831
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Polesov,

А зачем ассемблер?
Типа показать, что умеешь?
Или думаешь, так быстрее?
...
Рейтинг: 0 / 0
27.11.2020, 17:28
    #40022844
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU,
Такие вещи на ассемблере, как правило, быстрее.
В основном, за счет регистровой ручной оптимизации - нет обращений к стеку.
Ну, а показывать - не цель, чать не в детском садике )
...
Рейтинг: 0 / 0
27.11.2020, 17:51
    #40022850
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Polesov

Такие вещи на ассемблере, как правило, быстрее.
В основном, за счет регистровой ручной оптимизации - нет обращений к стеку.

AFAIK не всегда. Лично по моему опыту, компилятор значительно лучше оптимизирует последовательность инструкций (взаимовлияние), чем я.

Другое дело, что если использовать ASM, то тогда можно и MMX регистры использовать

Polesov

Mov ECX, 0Fh // количество итераций

Мне кажется, что задача должна решаться за log(32) операций, т.е. максимум 5 операций.
...
Рейтинг: 0 / 0
27.11.2020, 17:54
    #40022852
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Leonid Kudryavtsev,
согласен, надо смотреть в каждом конкретном случае.

Код: pascal
1.
  Mov ECX, 0Fh // количество итераций


Ну, это в лоб )
...
Рейтинг: 0 / 0
27.11.2020, 18:00
    #40022853
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Polesov,

Давай зарубимся
Я напишу ту же функцию на паскале и она будет быстрее :)
С меня паскалевский вариант, с тебя бенчмарк )
...
Рейтинг: 0 / 0
27.11.2020, 18:01
    #40022854
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Leonid Kudryavtsev,

А как ты решишь за 5 операций?
Интересно
...
Рейтинг: 0 / 0
27.11.2020, 18:06
    #40022855
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU,
хорошо, выкладывай код.

Да уже с кем-то гонялись - в каких-то случаях asm проиграл почти в 1.5 раза.
...
Рейтинг: 0 / 0
27.11.2020, 18:08
    #40022858
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Polesov,

Давай ты бенчмарк
Я часа через 2 подтянусь
...
Рейтинг: 0 / 0
27.11.2020, 18:21
    #40022861
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU
Необходимо объединить их так, чтобы биты шли последовательно
Я правильно понял, что из abc и xyz надо получить axbycz ?

SOFT FOR YOU
огромных заранее рассчитанных таблиц?
А если не огромных? 128 Кбайт - это огромная?
...
Рейтинг: 0 / 0
27.11.2020, 18:51
    #40022864
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
miksoft,

Да

Да

:)
...
Рейтинг: 0 / 0
27.11.2020, 19:03
    #40022868
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU
Polesov,
Давай ты бенчмарк

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
type
  TMixFunc = function ( w1, w2 : word ) : dWord;

function MixNop( w1, w2 : word ) : dWord; assembler; register;
asm
     Nop
end;

function MixAsm( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX    // обнуляем временный результат
     Mov     ECX,    01h    // устанавливаем маску единичного бита

@@10:
     Test    EAX,    01h    // проверяем бит для w1
     Jz      @@20

     Or      EBX,    ECX    // устанавливаем единичный бит w1

@@20:
     Shl     ECX,    01h    // сдвигаем маску единичного бита для w2
     Test    EDX,    01h    // проверяем бит для w2
     Jz      @@30

     Or      EBX,    ECX    // устанавливаем единичный бит w2

@@30:
     Shr     EAX,    01h    // сдвигаем w1 для проверки следующего бита
     Shr     EDX,    01h    // сдвигаем w2 для проверки следующего бита

     Shl     ECX,    01h    // сдвигаем маску единичного бита для w1
     Jecxz   @@40

     Jmp     @@10

@@40:
     Mov     EAX,    EBX

     Pop     EBX
end;

function MixPas( w1, w2 : word ) : dWord;
// реализация alekcvp
var
  i : integer;
  Mask : dWord;
begin
  Result := 0;
  for i := 15 downto 0 do
  begin
    Mask := 1 shl i;
    Result := Result shl 1 or DWORD(w1 and Mask) shl 1 or DWORD(w2 and Mask);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Nop : Int64;

  function Exec( Mix : TMixFunc ) : Int64;
  var
    t1, t2 : Int64;
    i : integer;
  begin
    QueryPerformanceCounter( t1 );
    for i := 1 to 1000000 do
      Mix( $1234, $4321 );
    QueryPerformanceCounter( t2 );
    Result := t2 - t1;
  end;

begin
  Nop := Exec( MixNop );
  Label1.Caption := 'Asm: ' + IntToStr( Exec( MixAsm ) - Nop );
  Label2.Caption := 'Pas: ' + IntToStr( Exec( MixPas ) - Nop );
end;



У меня получился выигрыш ~17%
...
Рейтинг: 0 / 0
27.11.2020, 19:08
    #40022869
rgreat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Вариант alekcvp мне нравиться больше.
...
Рейтинг: 0 / 0
27.11.2020, 19:08
    #40022870
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Корректность работы проверяли?
...
Рейтинг: 0 / 0
27.11.2020, 19:11
    #40022872
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
alekcvp
SOFT FOR YOU,

Ну у меня как-то так получилось в блокнотике:
Код: pascal
1.
2.
3.
4.
5.
6.
Result := 0; // DWORD;
for var i := 15 downto 0 do
begin
  Mask := 1 shl i; // Word
  Result := Result shl 1 or DWORD(WordA and Mask) shl 1 or DWORD(WordB and Mask);
end;



Почему "Result shl 1" ?
...
Рейтинг: 0 / 0
27.11.2020, 19:26
    #40022873
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Leonid Kudryavtsev
Корректность работы проверяли?

asm проверял
функцию alekcvp - нет (вместо нее SOFT FOR YOU обещался свою выложить)
...
Рейтинг: 0 / 0
27.11.2020, 19:33
    #40022876
SOFT FOR YOU
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
Та-даааа )

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
unit Unit1;

{$O+}

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TMixFunc = function ( w1, w2 : word ) : dWord;

function MixNop( w1, w2 : word ) : dWord; assembler; register;
asm
     Nop
end;

function MixAsm( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX    // обнуляем временный результат
     Mov     ECX,    01h    // устанавливаем маску единичного бита

@@10:
     Test    EAX,    01h    // проверяем бит для w1
     Jz      @@20

     Or      EBX,    ECX    // устанавливаем единичный бит w1

@@20:
     Shl     ECX,    01h    // сдвигаем маску единичного бита для w2
     Test    EDX,    01h    // проверяем бит для w2
     Jz      @@30

     Or      EBX,    ECX    // устанавливаем единичный бит w2

@@30:
     Shr     EAX,    01h    // сдвигаем w1 для проверки следующего бита
     Shr     EDX,    01h    // сдвигаем w2 для проверки следующего бита

     Shl     ECX,    01h    // сдвигаем маску единичного бита для w1
     Jecxz   @@40

     Jmp     @@10

@@40:
     Mov     EAX,    EBX

     Pop     EBX
end;

function MixPas( w1, w2 : word ) : dWord;
// реализация alekcvp
var
  i : integer;
  Mask : dWord;
begin
  Result := 0;
  for i := 15 downto 0 do
  begin
    Mask := 1 shl i;
    Result := Result shl 1 or DWORD(w1 and Mask) shl 1 or DWORD(w2 and Mask);
  end;
end;

function MixPlane(w1, w2 : word ) : dWord;
// реализация SoftForYou
var
  X: Cardinal;
begin
  X := (Cardinal(w2) shl 16) + Cardinal(w1);

  Result := Cardinal(w1) and (1 shl 0);
  Inc(Result, (X and (1 shl 1)) shl 1);
  Inc(Result, (X and (1 shl 2)) shl 2);
  Inc(Result, (X and (1 shl 3)) shl 3);
  Inc(Result, (X and (1 shl 4)) shl 4);
  Inc(Result, (X and (1 shl 5)) shl 5);
  Inc(Result, (X and (1 shl 6)) shl 6);
  Inc(Result, (X and (1 shl 7)) shl 7);
  Inc(Result, (X and (1 shl 8)) shl 8);
  Inc(Result, (X and (1 shl 9)) shl 9);
  Inc(Result, (X and (1 shl 10)) shl 10);
  Inc(Result, (X and (1 shl 11)) shl 11);
  Inc(Result, (X and (1 shl 12)) shl 12);
  Inc(Result, (X and (1 shl 13)) shl 13);
  Inc(Result, (X and (1 shl 14)) shl 14);
  Inc(Result, (X and (1 shl 15)) shl 15);
  Inc(Result, (X and (1 shl (16 + 0))) shr (16 + 0 - 1));
  Inc(Result, (X and (1 shl (16 + 1))) shr (16 + 1 - 1));
  Inc(Result, (X and (1 shl (16 + 2))) shr (16 + 2 - 1));
  Inc(Result, (X and (1 shl (16 + 3))) shr (16 + 3 - 1));
  Inc(Result, (X and (1 shl (16 + 4))) shr (16 + 4 - 1));
  Inc(Result, (X and (1 shl (16 + 5))) shr (16 + 5 - 1));
  Inc(Result, (X and (1 shl (16 + 6))) shr (16 + 6 - 1));
  Inc(Result, (X and (1 shl (16 + 7))) shr (16 + 7 - 1));
  Inc(Result, (X and (1 shl (16 + 8))) shr (16 + 8 - 1));
  Inc(Result, (X and (1 shl (16 + 9))) shr (16 + 9 - 1));
  Inc(Result, (X and (1 shl (16 + 10))) shr (16 + 10 - 1));
  Inc(Result, (X and (1 shl (16 + 11))) shr (16 + 11 - 1));
  Inc(Result, (X and (1 shl (16 + 12))) shr (16 + 12 - 1));
  Inc(Result, (X and (1 shl (16 + 13))) shr (16 + 13 - 1));
  Inc(Result, (X and (1 shl (16 + 14))) shr (16 + 14 - 1));
  Inc(Result, (X and (1 shl (16 + 15))) shr (16 + 15 - 1));
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Nop : Int64;

  function Exec( Mix : TMixFunc ) : Int64;
  var
    t1, t2 : Int64;
    i : integer;
  begin
    QueryPerformanceCounter( t1 );
    for i := 1 to 1000000 do
      Mix( $1234, $4321 );
    QueryPerformanceCounter( t2 );
    Result := t2 - t1;
  end;

begin
  Nop := Exec( MixNop );
  Label1.Caption := 'Asm: ' + IntToStr( Exec( MixAsm ) - Nop );
  Label2.Caption := 'Pas: ' + IntToStr( Exec( MixPas ) - Nop );
  Label3.Caption := 'Plane: ' + IntToStr( Exec( MixPlane ) - Nop );
end;

...
Рейтинг: 0 / 0
27.11.2020, 19:38
    #40022878
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOUогромных заранее рассчитанных таблиц?

Табличка в 256 word (то бишь 512 байт) - огромна?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.11.2020, 19:39
    #40022879
Polesov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Микширование бит
SOFT FOR YOU

Пример:

0101010101010101 op 1100111000111100 = 0111001001110110111001110010

Похоже, у меня ошибка - в ТЗ младший бит результата = младший бит 2-го аргумента
У меня наоборот.
Вот подправленный вариант (на скорость не влияет):
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
function MixAsm( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX    // обнуляем временный результат
     Mov     ECX,    01h    // устанавливаем маску единичного бита

@@10:
     Test    EDX,    01h    // проверяем бит для w2
     Jz      @@20

     Or      EBX,    ECX    // устанавливаем единичный бит w2

@@20:
     Shl     ECX,    01h    // сдвигаем маску единичного бита
     Test    EAX,    01h    // проверяем бит для w1
     Jz      @@30

     Or      EBX,    ECX    // устанавливаем единичный бит w1

@@30:
     Shl     ECX,    01h    // сдвигаем маску единичного бита
     Jecxz   @@40

     Shr     EAX,    01h    // сдвигаем w1 для проверки следующего бита
     Shr     EDX,    01h    // сдвигаем w2 для проверки следующего бита
     Jmp     @@10

@@40:
     Mov     EAX,    EBX

     Pop     EBX
end;


Результаты asm и pas совпадают.
...
Рейтинг: 0 / 0
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит / 25 сообщений из 104, страница 1 из 5
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]