Re: Byte-wise boolean optimisation
- From: Walter Banks <walter@xxxxxxxxxxxxx>
- Date: Thu, 31 May 2007 07:31:58 -0400
The following code will implement parallel and , or operations
on a byte or word var. This is approach works for CRC's
and other simple feedback polynomials.
Create a mask of the bits of interest say bits 0,1,3,7
#define b0 (1<<0)
#define b1 (1<<1)
#define b3 (1<<3)
#define b7 (1<<7)
mask = b0|b1|b3|b7;
/* parallel or operation between bits 0,1,3,7 */
or_result = ((var & mask) != 0);
/* parallel and operation between bits 0,1,3,7 */
and_result = ((var & mask) == mask);
The mask is a constant that is created at compile time
the parallel operations are quite quick.
Walter Banks
--
Byte Craft Limited
Tel. (519) 888-6911
http://www.bytecraft.com
walter@xxxxxxxxxxxxx
=================================================
Dave Hansen wrote:
Hopefully, I'm not completely missing your question...
On May 28, 8:44 am, Thomas Pircher <teh...@xxxxxxx> wrote:
Hi all,
I'm wondering if there exist algorithms for byte-wise boolean optimisation,
much like the Quine-McCluskey works for a single bit.
Basically I have 8 truth-functions f7(.) ... f0(.) representing the bits
7..0 of the result byte, and I would like to find an optimised function
f(.) which gives the same result as the single-bit-functions together and
uses 8-bit parallel boolean operators.
Obviously I can write
f(.) = f7(.) << 7 | f6(.) << 6 | ... | f0(.)
but this is not very elegant. Is this a common problem that someone has
solved in a better way than my straight-forward (naive) attempt?
Well, straight-forward is a Good Thing (tm) IMHO. And there's really
little you can do to improve on your code above. After all, you still
have to call each function in order to get all the bits, and you have
to associate each bit with the correct function.
You are potentially wasting time with the shift operators (depending
on how smart your compiler is). I'd probably write a function like
unsigned char get_byte()
{
unsigned char result = 0;
if (f0()) result = 0x01;
if (f1()) result |= 0x02;
if (f2()) result |= 0x04;
<etc.>
if (f7()) result |= 0x80;
return result;
}
Not an elegant one-liner, but it should generate nearly optimal code.
If you want a statement rather than a function, you could do something
like
byte = (f0()? 0x01: 0) | (f1? 0x02: 0) | (f2()? 0x04: 0) <etc> |
(f7()? 0x80: 0);
But that's not much better than your original, but it at least avoids
the shifts if the compiler can't figure out that f0..f7 return single-
bit values.
If you want to get really crazy with the syntax, you could try
#define f_bit(n) (f ## n()? (1<<n): 0)
byte = f_bit(0) | f_bit(1) | f_bit(2) | <etc.> | f_bit(7);
But don't expect future maintainers to think kindly of you...
WARNING: all code untested. HTH,
-=Dave
.
- References:
- [OT] Byte-wise boolean optimisation
- From: Thomas Pircher
- Re: Byte-wise boolean optimisation
- From: Dave Hansen
- [OT] Byte-wise boolean optimisation
- Prev by Date: Re: What's more important optimisations or debugging?
- Next by Date: Re: What's more important optimisations or debugging?
- Previous by thread: Re: Byte-wise boolean optimisation
- Next by thread: Ethernet daisy chaining
- Index(es):
Relevant Pages
|
