Re: Byte-wise boolean optimisation

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

.