Thu, 10 Sep 2020 10:34:18 -0700 (PDT)

Related articles |
---|

[4 earlier articles] |

Re: Bit swizzling davidlovemore@gmail.com (davidl...@gmail.com) (2020-09-06) |

Re: Bit Swizzling xxx.syseng.yyy@gfsys.co.uk (Chris) (2020-09-06) |

Re: Bit swizzling martin@gkc.org.uk (Martin Ward) (2020-09-07) |

Re: Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-07) |

Re: Bit swizzling DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2020-09-08) |

Re: Bit swizzling tomcrick@gmail.com (Tom Crick) (2020-09-08) |

Re: Bit swizzling gah4@u.washington.edu (gah4) (2020-09-10) |

Re: Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-10) |

From: | gah4 <gah4@u.washington.edu> |

Newsgroups: | comp.compilers |

Date: | Thu, 10 Sep 2020 10:34:18 -0700 (PDT) |

Organization: | Compilers Central |

References: | 20-09-014 |

Injection-Info: | gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="67222"; mail-complaints-to="abuse@iecc.com" |

Keywords: | optimize, hardware |

Posted-Date: | 10 Sep 2020 13:55:01 EDT |

In-Reply-To: | 20-09-014 |

On Saturday, September 5, 2020 at 9:45:43 AM UTC-7, Rick C. Hodgin wrote:

*> Are there any algorithms which take a known-at-compile-time sequence*

*> of bitwise operations on an 8-bit to 64-bit quantity, and optimize*

*> them down to their minimal set of operations?*

*>*

*> For example, if I have an 8-bit byte and I want to swizzle the bits*

*> thusly:*

*>*

*> Input: 07 06 05 04 03 02 01 00*

*> Output: 05 04 07 02 01 03 00 06*

There is a lot of work, and many algorithms, for logic optimization,

or minimization, that, for example, will find the optimal combination

of NAND and NOR gates to evaluate some logical operation.

This is used to compile Verilog or VHDL into either FPGA bit files

or ASIC masks. On the other hand, logic minimization tends to

believe that you can wire anything to anything else. That is, bit

swizzle is just wiring. The question you ask doesn't come up.

(Later on, routing has to get all the wires to the appropriate

place, but that is true in general, not just for this case.)

Note that it isn't just adjacent bits, but bits with the same spacing

in the input and output, such that you can mask with AND, shift,

and combine with OR. I suspect that with the operations usually

available: AND, OR, XOR, and shift, it wouldn't be hard to find an

algorithm for the optimal case. If you add more operations,

maybe allow also add and multiply, it gets interesting.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.