[OT] Byte-wise boolean optimisation

I'm unclear - do you want a one byte answer, from an 8 byte variable set, and you want to use common byte-wide operators, to get to the answer ? Sounds a fairly big ask, as you will need 'leave alone' operations many times.

You could easily feed the eqns into any CPLD/FPGA tool flow, and inspect the output eqns for each bit, which will of course be optimised, but using bit operators. Then, you could work backwards, to see if any can be merged into multi-bit operations. Atmels WinCUPL has choices of optimise.

-jg

Hi Jim,

fortunately my case is slightly simpler. I have one input byte and one output byte and a given algorithm to transform the former into the latter, but I want to simplify the algorithm to use just logic operators (instead of loops).

To be more precise, I'm working on a source code generator for CRC checks

With commonly used Polys (which happen to not contain too many ones) it does not look so bad. But for other Polys, I get terribly long expressions.

This will lead to the following approach: Quine-McCluskey (and Petrick's algorithm) for all 8 output bits and then finding some common patterns in the resulting sums of products, based on heuristics (e.g. the 'sum of product' for one bit is often similar to the sum of products of an adjacent bit, just shifted by one).

Ok, I admit it, I was asking for the silver bullet, but I see I have to go down the hard way. :-) Any suggestions are more than welcome!

Cheers, Thomas

We have looked at this in the context of compiler processing of booleans. Parallel and's and ors are quite easy. Generic boolean expressions are a lot more difficult to accomplish and there is no general solution that I know of. We do check in our compilers if boolean bits are in the same byte (or processor native word size) and generate code that take advantage of this for simple and and or operations.

w..

Thomas Pircher wrote:

The most simple way to do that is to use a table. Use your f1..8() functions to create the table either at runtime or at compiletime, whatever fits better.

This is a highly interesting subject to me, so please avoid top-posting. Your answer belongs after (or intermixed with) the quoted material to which you reply, after snipping all irrelevant material. See the following links:

Oh FFS. CBF, please give this newsgroup-policing mania of yours a rest! It's getting tiresome, to the point that I'm considering plonking you, which would be a shame given the quality of the signal (despite the noise) you occasionally put out.

Steve

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; 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) | (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

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 > much like the Quine-McCluskey works for a single bit.