Prev: Apple II Debugger
Next: TMA Assembler?
From: Evenbit on 19 Aug 2006 15:58

Skybuck wrote:
> Evenbit schreef:
>
> > Skybuck wrote:
> > > So what would be the fastest way in pure delphi code to reverse the
> > > bits ?
> > >
> >
> > Well, first, minimize the number of times you actually need to run
> > through the complete algo. Check the input to see if the bit-pattern
> > is symetrical or not. If it is symetrical, then you don't need to flip
> > it. Examples:
> >
> > 11111111
> > 00000000
> > 11000011
> > 00111100
> > 00011000
> > 11100111
> > 10100101
> >
> > etc....
> >
> > Nathan.
>
> Dude,
>
> Come back when you have a real/workable algorithm/idea ! ;)
>
> This idea of yours is only half of an algorithm/solution ! ;)
>
> Where's the rest ?!!!! =D
>

I charge a fee for that. ;)

Nathan.

From: f0dder on 19 Aug 2006 16:11
A 256-byte LUT can easily fit in any CPU L1 cache. Typically a cacheline is
32 bytes long, so you'd maximally get (256/32) 8 cache misses before the
entire LUT is cached. I'm pretty sure that this is hard to beat no matter
which fancy instruction set you're going to use...



From: Evenbit on 19 Aug 2006 16:20

Skybuck wrote:
> Hello Folks,

You have lost the privledge to refer to us as "folks", but we will
gladly refer to you as a loser, Delphi code-monkey, programmer wannabe
who is afraid to learn anything about computers. It is sad that your
technology phobia causes you to act like such a fool in front of
everyone and prevents you from reading the appropriate literature so
that you can understand something about the machine you want to work
with.

Nathan.

From: alanglloyd on 19 Aug 2006 16:42

Skybuck wrote:
> alanglloyd(a)aol.com schreef:
>
<snip>
> Try re-entering the competition with faster implementations which work
> on a single byte only ! ;) =D
>
> You last man ! =D
>

type
T8BitByte = 0..7;
T8BitByteSet = set of T8BitByte;

function SwapBits(InByte : byte) : byte;
var
I : T8BitByte;
InBits, OutBits : T8BitByteSet;
const
RevArray : array[T8BitByte] of T8BitByte
= ( 7, 6, 5, 4, 3, 2, 1, 0);
begin
InBits := T8BitByteSet(InByte);
OutBits := [];
for I := 0 to 7 do
if I in InBits then
Include(OutBits, RevArray[I]);
Result := byte(OutBits);
end;

Alan Lloyd

From: jukka@liimatta.org on 19 Aug 2006 21:42
inline uint32 reverse(uint32 v)
{
// reverse bit order
// original implementation by Steve Baker

v = ((v >> 1) & 0x55555555) | ((v << 1) & 0xaaaaaaaa);
v = ((v >> 2) & 0x33333333) | ((v << 2) & 0xcccccccc);
v = ((v >> 4) & 0x0f0f0f0f) | ((v << 4) & 0xf0f0f0f0);
v = ((v >> 8) & 0x00ff00ff) | ((v << 8) & 0xff00ff00);
v = (v >> 16) | (v << 16);

return v;
}

23 AOPS, quite a big number but we are avoiding memory access
completely. At 25% extra cost the width is extended to 64 bits. :)

Problem: a lot of dependencies to previous statement, but atleast the
left and right shift sides are possible to run concurrently (thinking
of decoded instructions).

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Prev: Apple II Debugger
Next: TMA Assembler?