Есть ли простой способ битового отражения байтовой переменной в Delphi, так что старший бит (MSB) получает младший значащий бит (LSB) и наоборот?
Как я могу отразить байт в Delphi?
Ответ 1
В коде вы можете сделать это следующим образом:
function ReverseBits(b: Byte): Byte;
var
i: Integer;
begin
Result := 0;
for i := 1 to 8 do
begin
Result := (Result shl 1) or (b and 1);
b := b shr 1;
end;
end;
Но таблица поиска будет намного более эффективной и будет потреблять только 256 байт памяти.
function ReverseBits(b: Byte): Byte; inline;
const
Table: array [Byte] of Byte = (
0,128,64,192,32,160,96,224,16,144,80,208,48,176,112,240,
8,136,72,200,40,168,104,232,24,152,88,216,56,184,120,248,
4,132,68,196,36,164,100,228,20,148,84,212,52,180,116,244,
12,140,76,204,44,172,108,236,28,156,92,220,60,188,124,252,
2,130,66,194,34,162,98,226,18,146,82,210,50,178,114,242,
10,138,74,202,42,170,106,234,26,154,90,218,58,186,122,250,
6,134,70,198,38,166,102,230,22,150,86,214,54,182,118,246,
14,142,78,206,46,174,110,238,30,158,94,222,62,190,126,254,
1,129,65,193,33,161,97,225,17,145,81,209,49,177,113,241,
9,137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,
5,133,69,197,37,165,101,229,21,149,85,213,53,181,117,245,
13,141,77,205,45,173,109,237,29,157,93,221,61,189,125,253,
3,131,67,195,35,163,99,227,19,147,83,211,51,179,115,243,
11,139,75,203,43,171,107,235,27,155,91,219,59,187,123,251,
7,135,71,199,39,167,103,231,23,151,87,215,55,183,119,247,
15,143,79,207,47,175,111,239,31,159,95,223,63,191,127,255
);
begin
Result := Table[b];
end;
Это более чем в 10 раз быстрее, чем версия кода, которая работает с отдельными битами.
Наконец, я обычно не комментирую слишком негативно о принятых ответах, когда у меня есть конкурирующий ответ. В этом случае есть очень серьезные проблемы с ответом, который вы приняли, что я хотел бы четко заявить вам, а также для любых будущих читателей.
Вы приняли ответ @Arioch в то время, когда он содержал тот же код Pascal, что и в этом ответе, вместе с двумя версиями ассемблера. Оказывается, эти версии ассемблера намного медленнее, чем версия Pascal. Они в два раза медленнее, чем код Pascal.
Это обычная ошибка, заключающаяся в том, что преобразование кода высокого уровня в ассемблер приводит к более быстрому коду. Если вы делаете это плохо, вы можете легко создать код, который работает медленнее, чем код, испускаемый компилятором. Бывают моменты, когда стоит писать код в ассемблере, но вы не должны этого делать без надлежащего бенчмаркинга.
Что особенно важно для использования ассемблера здесь, так это то, что это настолько очевидно, что решение на основе таблицы будет чрезвычайно быстрым. Трудно представить, как это можно было бы значительно улучшить.
Ответ 2
function ByteReverseLoop(b: byte): byte;
var i: integer;
begin
Result := 0; // actually not needed, just to make compiler happy
for i := 1 to 8 do
begin
Result := Result shl 1;
if Odd(b) then Result := Result or 1;
b := b shr 1;
end;
end;
Если скорость важна, вы можете использовать таблицу поиска. Вы чувствуете это один раз при запуске программы, а затем вы просто берете значение из таблицы. Так как вам нужно всего лишь байт байт, это займет 256x1 = 256 байт памяти. И учитывая, что последние версии Delphi поддерживают встроенные функции, которые обеспечивали бы скорость, читаемость и надежность (инкапсулирующий поиск массива в функции, вы можете быть уверены, что не измените значения из-за некоторой опечатки)
Var ByteReverseLUT: array[byte] of byte;
function ByteReverse(b: byte): byte; inline;
begin Result := ByteReverseLUT[b] end;
{Unit/program initialization}
var b: byte;
for b := Low(ByteReverseLUT) to High(ByteReverseLUT)
do ByteReverseLUT[b] := ByteReverseLoop(b);
Сравнение скорости нескольких реализаций, упомянутых на этом форуме.
AMD Phenom2 x710/Win7 x64/Delphi XE2 32-бит {$ O +}
Pascal AND original: 12494
Pascal AND reversed: 33459
Pascal IF original: 46829
Pascal IF reversed: 45585
Asm SHIFT 1: 15802
Asm SHIFT 2: 15490
Asm SHIFT 3: 16212
Asm AND 1: 19408
Asm AND 2: 19601
Asm AND 3: 19802
Паскаль И развернут: 10052 Asm Shift развернут: 4573 LUT, названный: 3192 Математика Паскаля, названная: 4614
Примечание. Временные диаграммы LUT (lookup table), вероятно, довольно оптимистичны. Из-за работы в узком цикле вся таблица была втянута в кеш процессора L1. В реальных вычислениях эта функция, скорее всего, будет называться гораздо реже, а кеш L1 не будет полностью хранить таблицу.
Результат вызывных функций Pascal в подстроке - фиктивные - Delphi не вызывал их, обнаружив, что у них не было побочных эффектов. Но смешно - тайминг был другим.
Asm Shift unrolled: 4040
LUT, called: 3011
LUT, inlined: 977
Pascal unrolled: 10052
Pas. unrolled, inlined: 849
Pascal math, called: 4614
Pascal math, inlined: 6517
И ниже объяснения:
Project1.dpr.427: d := BitFlipLUT(i)
0044AC45 8BC3 mov eax,ebx
0044AC47 E89CCAFFFF call BitFlipLUT
Project1.dpr.435: d := BitFlipLUTi(i)
Project1.dpr.444: d := MirrorByte(i);
0044ACF8 8BC3 mov eax,ebx
0044ACFA E881C8FFFF call MirrorByte
Project1.dpr.453: d := MirrorByteI(i);
0044AD55 8BC3 mov eax,ebx
Project1.dpr.460: d := MirrorByte7Op(i);
0044ADA3 8BC3 mov eax,ebx
0044ADA5 E8AEC7FFFF call MirrorByte7Op
Project1.dpr.462: d := MirrorByte7OpI(i);
0044ADF1 0FB6C3 movzx eax,bl
Все вызовы встроенных функций были устранены. Однако про передачу параметров Delphi было принято три разных решения:
- Для первого вызова он устраняет параметр, передаваемый вместе с вызовом функции
- Для второго вызова он продолжал передачу параметров, несмотря на то, что функция не вызывалась
- Для 3-го вызова он продолжал изменять передачу параметров, которая оказалась дольше, чем вызов функции! Weird!: -)
Ответ 3
function BitFlip(B: Byte): Byte;
const
N: array[0..15] of Byte = (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15);
begin
Result := N[B div 16] or N[B mod 16] shl 4;
end;
Ответ 4
Использование грубой силы может быть простым и эффективным.
Эта подпрограмма НЕ в с решением David LUT.
Обновление
Добавлен массив байтов в качестве входных данных и результат, присвоенный массиву байтов. Это показывает лучшую производительность для решения LUT.
function MirrorByte(b : Byte) : Byte; inline;
begin
Result :=
((b and $01) shl 7) or
((b and $02) shl 5) or
((b and $04) shl 3) or
((b and $08) shl 1) or
((b and $10) shr 1) or
((b and $20) shr 3) or
((b and $40) shr 5) or
((b and $80) shr 7);
end;
Обновление 2
Поймать немного, нашел BitReverseObvious.
function MirrorByte7Op(b : Byte) : Byte; inline;
begin
Result :=
{$IFDEF WIN64} // This is slightly better in x64 than the code in x32
(((b * UInt64($80200802)) and UInt64($0884422110)) * UInt64($0101010101)) shr 32;
{$ENDIF}
{$IFDEF WIN32}
((b * $0802 and $22110) or (b * $8020 and $88440)) * $10101 shr 16;
{$ENDIF}
end;
Этот подход ближе к решению LUT, даже быстрее в одном тесте.
Подводя итог, MirrorByte7Op() на 5-30% медленнее, чем LUT, в 3 тестах, на 5% быстрее в одном тесте.
Код для сравнения:
uses
System.Diagnostics;
const
cBit : Byte = $AA;
cLoopMax = 1000000000;
var
sw : TStopWatch;
arrB : array of byte;
i : Integer;
begin
SetLength(arrB,cLoopMax);
for i := 0 TO Length(arrB) - 1 do
arrB[i]:= System.Random(256);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := b;
end;
sw.Stop;
WriteLn('Loop ',b:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := ReflectBits(arrB[i]);
end;
sw.Stop;
WriteLn('RB array in: ',b:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := MirrorByte(arrB[i]);
end;
sw.Stop;
WriteLn('MB array in: ',b:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := MirrorByte7Op(arrB[i]);
end;
sw.Stop;
WriteLn('MB7Op array in : ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
arrB[i] := ReflectBits(arrB[i]);
end;
sw.Stop;
WriteLn('RB array in/out: ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
arrB[i]:= MirrorByte(arrB[i]);
end;
sw.Stop;
WriteLn('MB array in/out: ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
arrB[i]:= MirrorByte7Op(arrB[i]);
end;
sw.Stop;
WriteLn('MB7Op array in/out: ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
ReadLn;
end.
Результат теста (XE3, i7 CPU 870):
32 bit 64 bit
--------------------------------------------------
Byte assignment (= empty loop) 599 ms 2117 ms
MirrorByte to byte, array in 6991 ms 8746 ms
MirrorByte7Op to byte, array in 1384 ms 2510 ms
ReverseBits to byte, array in 945 ms 2119 ms
--------------------------------------------------
ReverseBits array in/out 1944 ms 3721 ms
MirrorByte7Op array in/out 1790 ms 3856 ms
BitFlipNibble array in/out 1995 ms 6730 ms
MirrorByte array in/out 7157 ms 8894 ms
ByteReverse array in/out 38246 ms 42303 ms
Я добавил некоторые другие предложения в последнюю часть таблицы (все вложенные). Вероятно, наиболее справедливо проверить в цикле с массивом и массивом. ReverseBits (LUT) и MirrorByte7Op сравнимы по скорости, за которыми следует BitFlipNibble (LUT), которая хуже соответствует бит x64.
Примечание. Я добавил новый алгоритм для 64-разрядной части x64 MirrorByte7Op. Он лучше использует 64-битные регистры и имеет меньше инструкций.