Reversing bit order in delphi ? (unmoderated)
in [ASM]
|
Prev: Apple II Debugger
Next: TMA Assembler?
From: Skybuck on 22 Aug 2006 11:29 Andreas Kochenburger schreef: > On 22 Aug 2006 07:50:17 -0700, "Shark8" <OneWingedShark(a)gmail.com> > wrote: > > >Here you are Skybuck, my version on the bit-reversal. It's pure Delphi, > >and admitedly similar to some that have been submitted (but then > >there's only a limited number of ways to do a specific task correctly), > >but may be insightful. > > For fun here's a pretty fast algo for 32-bit in C which compiles > easily into efficient machine code. > > unsigned int > revere (register unsigned int x) > { > x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); > x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); > x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); > x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); > return((x >> 16) | (x << 16)); > } > > A linear lookup-table lookup would be impossibly large. > > A comparison of a similar code generated by gcc versus Delphi, > GnuPascal and FreePascal would be interesting. Who could do that? I have already seen this code/algorithm. I consider it obfuscated. This can be easily seen from the x being manipulated twice and then assigned. Furthermore the compiler generates wacky assembler instructions which do not represent the C or Delphi code. Furthermore it's difficult to tell how the C/Delphi code works. Can you explain the algorithm that the C code uses ? Can you "unraffle" it into multiple lines (without all the () ) ? Bye, Skybuck.
From: Terry Russell on 22 Aug 2006 13:41 "Andreas Kochenburger" <akk(a)nospam.com> wrote in message news:uu7me2tk1cje29lmbu8kr2415ar3ptitts(a)4ax.com... > On 22 Aug 2006 07:50:17 -0700, "Shark8" <OneWingedShark(a)gmail.com> > wrote: > > For fun here's a pretty fast algo for 32-bit in C which compiles > easily into efficient machine code. > > unsigned int > revere (register unsigned int x) > { > x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); > x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); > x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); > x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); > return((x >> 16) | (x << 16)); > } > > A linear lookup-table lookup would be impossibly large. > > A comparison of a similar code generated by gcc versus Delphi, > GnuPascal and FreePascal would be interesting. Who could do that? rough figure using rdtsc count Delphised code , integer loop and cardinal call x100M elapsed 2334007226 average 23 24 for 256 calls no code loop call average 2 so , quite fast if you are looking at a few thousand calls , less than it takes to load a lut but compared to 5 individual to move the results from the table once calculated or nearer zero actual average for a large number in a loop, given the loop and piping code loop x 100M 201556288 av 2 code loop++lookup x100M 202085754 av 2 piping, architecture verison, manufacturer,cache, ...unless you can rigourously control the environment , throw out flexibility and introduce machine dependancy, you cannot ever be sure what the last few clocks will be Not that it matters realtively, I just generated 100 gig of useless data because of a bad setting, a few clocks seems quite trivial. I wonder how much of available cpu ticks in the world actually go to a good purpose? I suspect it is less than 0.01% :-)
From: f0dder on 22 Aug 2006 16:01 Skybuck wrote: > f0dder schreef: >> Any instruction that references memory will cause an entire cache >> line to be read (or written?). Iirc it's been like this since at >> least the 486. Things are a bit more complex than this, though, >> especially on recent architectures... check the intel and AMD docs, >> and Agner Fog's optimization manuals. > > What exactly is a cache line ? > > Is this like a "line of memory" in the neighbourhood of where the data > from/to the memory address was read/written ? A cache line is the smallest amount of memory the CPU will exchange with the RAM. It can vary, but 32 bytes seems to be pretty common. When you access memory at, say, physical address 15, the cache line from 0-31 will be read, modified and written back... well, basically. It's a bit more complex than that :)
From: f0dder on 22 Aug 2006 16:05 Skybuck wrote: > I have already seen this code/algorithm. I consider it obfuscated. It's not obfuscated, it just happens to do "trickery bit magic". Just like things like agner fog's strlen implementation. > Furthermore the compiler generates wacky assembler instructions which > do not represent the C or Delphi code. Really? > Furthermore it's difficult to tell how the C/Delphi code works. A bit (hehe). I haven't bothered to do it, but it might help if you look at the hex numbers in binary notation.
From: f0dder on 22 Aug 2006 16:06
Andreas Kochenburger wrote: > A linear lookup-table lookup would be impossibly large. But you could do byte-lookups and shuffle them into their right places... wonder if that'll be faster than the BitMagic code, though... |