Path: csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: "davidl...@gmail.com" Newsgroups: comp.compilers Subject: Re: Bit swizzling Date: Sun, 6 Sep 2020 00:31:53 -0700 (PDT) Organization: Compilers Central Lines: 32 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <20-09-018@comp.compilers> References: <20-09-014@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="58182"; mail-complaints-to="abuse@iecc.com" Keywords: optimize Posted-Date: 06 Sep 2020 11:43:12 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <20-09-014@comp.compilers> Xref: csiph.com comp.compilers:2589 On Saturday, September 5, 2020 at 5:45:43 PM UTC+1, 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? There's some good resources on bit permutations including this online calculator here: http://programming.sirrida.de/calcperm.php For: > Input: 07 06 05 04 03 02 01 00 > Output: 05 04 07 02 01 03 00 06 It gives: x = bit_permute_step_simple(x, 0x55555555, 1); // Bit index complement 0 x = bit_permute_step_simple(x, 0x33333333, 2); // Bit index complement 1 x = bit_permute_step_simple(x, 0x0f0f0f0f, 4); // Bit index complement 2 where t_bits bit_permute_step_simple(t_bits x, t_bits m, t_uint shift) { return ((x & m) << shift) | ((x >> shift) & m); } Approx 12 cycles on superscalar processor. Source code for a more sophisticated permutation code generator is also available linked from the page. Some notes here on the online generator: http://programming.sirrida.de/bit_perm.html#calculator