Re: [OT] Byte-wise boolean optimisation

"CBFalconer" <cbfalconer@xxxxxxxxx> wrote in message
news:465C7FF2.E31061B6@xxxxxxxxxxxx
Walter Banks wrote: *** and top-posted - fixed ***
Thomas Pircher wrote:

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?

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.

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:

--
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/> (taming google)
<http://members.fortunecity.com/nnqweb/> (newusers)

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
http://www.fivetrees.com


.

Relevant Pages

  • Re: Negation of boolean
    ... >compiler take advantage of this and always compile!b to b^true? ... The catch is, if you get too fancy with optimisation in Javac, the ... where x is a boolean could be compiled with a single Pentium NOT ...
    (comp.lang.java.help)
  • Re: [OT] Byte-wise boolean optimisation
    ... We have looked at this in the context of compiler processing of ... compilers if boolean bits are in the same byte (or processor ... I'm wondering if there exist algorithms for byte-wise boolean optimisation, ... uses 8-bit parallel boolean operators. ...
    (comp.arch.embedded)
  • Re: [OT] Byte-wise boolean optimisation
    ... optimisation, much like the Quine-McCluskey works for a single bit. ... bit-functions together and uses 8-bit parallel boolean operators. ... We have looked at this in the context of compiler processing of ...
    (comp.arch.embedded)