Bit Swizzling

From	"Rick C. Hodgin" <rick.c.hodgin@nospicedham.gmail.com>
Newsgroups	comp.lang.c, comp.arch, comp.arch.fpga, comp.lang.asm.x86
Subject	Bit Swizzling
Date	2020-09-04 20:33 -0400
Organization	Liberty Software Foundation
Message-ID	<riumcj$3j9$1@dont-email.me> (permalink)

Cross-posted to 4 groups.

Show all headers | View raw

I'm not sure where to ask this question, so I pushed it out to several
groups.  You need not reply to all of them if you don't think it is a
topical subject.

I included comp.compilers in a previous message, but it apparently holds
the message until it passes moderation.  So, I've not included it here.
A duplicate message may post if/when the comp.compilers moderator John
Levine approves it.

-----
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

I can easily swizzle the data using a brute force method:

     v = get_value();
     o = 0;
     swizzle1(o, v, 0, 6);
     swizzle1(o, v, 1, 0);
     swizzle1(o, v, 2, 3);
     swizzle1(o, v, 3, 1);
     swizzle1(o, v, 4, 2);
     swizzle1(o, v, 5, 7);
     swizzle1(o, v, 6, 4);
     swizzle1(o, v, 7, 5);

     // Untested, off the top of my head
     void swizzle(unsigned char& o, unsigned char v, int s, int d)
     {
         o |= (((v & (1 << s)) >> s) << d);
     }

And, of course, that algorithm can be optimized based on relative
values of s and d, and if s is 0, etc.

However, there also exists a minimal set of steps to complete that
swizzling because in the operation above, bits 5 and 4 are used in
sequence.  It could be done using a swizzle2() operation, for example
and handle 2 bits at a time.

Are there any existing algorithms which examine the operations that
must be conducted and the optimized / minimal sequence of steps to
conduct it?

Thank you in advance.

-- 
Rick C. Hodgin

Back to comp.lang.c | Previous | Next — Next in thread | Find similar

Thread

Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@nospicedham.gmail.com> - 2020-09-04 20:33 -0400
  Re: Bit Swizzling Bart <bc@freeuk.com> - 2020-09-05 12:36 +0100
    Re: Bit Swizzling Bart <bc@freeuk.com> - 2020-09-05 15:30 +0100
      Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-05 11:29 -0400
        Re: Bit Swizzling Bart <bc@freeuk.com> - 2020-09-05 20:28 +0100
    Re: Bit Swizzling kegs@provalid.com (Kent Dickey) - 2020-09-05 11:35 -0500
  Re: Bit Swizzling Bart <bc@nospicedham.freeuk.com> - 2020-09-05 12:33 +0100
  Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-05 20:55 +0200
    Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-05 15:18 -0400
      Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-06 10:17 +0200
        Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-07 07:06 +0000
          Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-07 10:35 +0200
            Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-07 11:01 -0400
              Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-07 20:07 +0200
                Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-07 14:19 -0400
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-07 20:39 +0200
                Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-07 15:13 -0400
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 12:21 +0200
                Re: Bit Swizzling Bart <bc@freeuk.com> - 2020-09-08 12:51 +0100
                Re: Bit Swizzling Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-09-08 05:18 -0700
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 15:20 +0200
                Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-08 15:56 +0000
                Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-08 12:17 -0400
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 19:31 +0200
                Re: Bit Swizzling olcott <NoOne@NoWhere.com> - 2020-09-08 12:46 -0500
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 19:53 +0200
                Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-08 15:13 -0400
                Re: Bit Swizzling (c++ versus c) olcott <NoOne@NoWhere.com> - 2020-09-08 14:59 -0500
                Re: Bit Swizzling (c++ versus c) "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-08 21:45 -0400
                Re: Bit Swizzling (c++ versus c) olcott <NoOne@NoWhere.com> - 2020-09-08 20:56 -0500
                Re: Bit Swizzling (c++ versus c) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-09-08 19:49 -0700
                Re: Bit Swizzling (c++ versus c) Juha Nieminen <nospam@thanks.invalid> - 2020-09-09 06:27 +0000
                Re: Bit Swizzling (c++ versus c) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-09-09 06:38 +0000
                Re: Bit Swizzling (c++ versus c) David Brown <david.brown@hesbynett.no> - 2020-09-09 11:54 +0200
                Re: Bit Swizzling (c++ versus c) olcott <NoOne@NoWhere.com> - 2020-09-09 09:21 -0500
                Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-08 16:31 +0000
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 19:35 +0200
                Re: Bit Swizzling olcott <NoOne@NoWhere.com> - 2020-09-08 12:50 -0500
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 19:53 +0200
                Re: Bit Swizzling olcott <NoOne@NoWhere.com> - 2020-09-08 13:09 -0500
                Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-08 18:48 +0000
                Re: Bit Swizzling + [HP] olcott <NoOne@NoWhere.com> - 2020-09-08 14:09 -0500
                Re: Bit Swizzling + [HP] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-09-08 12:37 -0700
                Re: Bit Swizzling + [x86utm] olcott <NoOne@NoWhere.com> - 2020-09-08 16:59 -0500
                Re: Bit Swizzling + [HP] olcott <NoOne@NoWhere.com> - 2020-09-08 18:13 -0500
                Re: Bit Swizzling + [HP] olcott <NoOne@NoWhere.com> - 2020-09-08 20:07 -0500
                Re: Bit Swizzling + (HP refutation criteria) olcott <NoOne@NoWhere.com> - 2020-09-09 20:10 -0500
                Re: Bit Swizzling + [HP] olcott <NoOne@NoWhere.com> - 2020-09-09 21:07 -0500
                Re: Bit Swizzling + [HP refutation criteria] olcott <NoOne@NoWhere.com> - 2020-09-09 21:30 -0500
                Re: Bit Swizzling + [HP refutation criteria] olcott <NoOne@NoWhere.com> - 2020-09-09 21:39 -0500
                Re: Bit Swizzling + [HP] olcott <NoOne@NoWhere.com> - 2020-09-10 22:48 -0500
                Re: Bit Swizzling Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-08 13:06 -0700
                Re: Bit Swizzling Bart <bc@freeuk.com> - 2020-09-08 19:37 +0100
                Re: Bit Swizzling David Brown <david.brown@hesbynett.no> - 2020-09-09 12:04 +0200
                Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-08 18:39 +0000
                Re: Bit Swizzling Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-09-08 12:27 -0700
                Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-07 15:47 -0400
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 12:23 +0200
            Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-08 00:07 +0000
              Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 12:26 +0200
                Re: Bit Swizzling scott@slp53.sl.home (Scott Lurndal) - 2020-09-08 15:50 +0000
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 19:06 +0200
                Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-08 13:13 -0400
                Re: Bit Swizzling olcott <NoOne@NoWhere.com> - 2020-09-08 12:18 -0500
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 19:28 +0200
                Re: Bit Swizzling Bart <bc@freeuk.com> - 2020-09-08 18:51 +0100
                Re: Bit Swizzling olcott <NoOne@NoWhere.com> - 2020-09-08 13:02 -0500
                Re: Bit Swizzling Bonita Montero <Bonita.Montero@gmail.com> - 2020-09-08 20:45 +0200
                Re: Bit Swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-08 15:55 +0000
  Re: Bit Swizzling olcott <NoOne@nospicedham.NoWhere.com> - 2020-09-08 11:25 -0500
    Re: Bit Swizzling olcott <NoOne@nospicedham.NoWhere.com> - 2020-09-08 11:50 -0500
    Re: Bit Swizzling Kaz Kylheku <793-849-0957@nospicedham.kylheku.com> - 2020-09-08 17:47 +0000
  Re: Bit Swizzling "R.Wieser" <address@nospicedham.not.available> - 2020-09-08 20:26 +0200
    Re: Bit Swizzling David Brown <david.brown@nospicedham.hesbynett.no> - 2020-09-08 22:00 +0200
    Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@nospicedham.gmail.com> - 2020-09-08 21:51 -0400
      Re: Bit Swizzling "R.Wieser" <address@nospicedham.not.available> - 2020-09-09 10:53 +0200

csiph-web