Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #61300 > unrolled thread

Bit Swizzling

Back to article view | Back to comp.arch

Contents

  Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@nospicedham.gmail.com> - 2020-09-04 20:33 -0400
    Re: Bit Swizzling MitchAlsup <MitchAlsup@aol.com> - 2020-09-04 18:26 -0700
      Re: Bit Swizzling MitchAlsup <MitchAlsup@aol.com> - 2020-09-04 18:27 -0700
    Re: Bit Swizzling Joshua Landau <joshua.landau.ws@gmail.com> - 2020-09-04 20:32 -0700
      Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-05 09:16 -0400
    Re: Bit Swizzling Bart <bc@nospicedham.freeuk.com> - 2020-09-05 12:33 +0100
    Re: Bit Swizzling Chris <xxx.syseng.yyy@gfsys.co.uk> - 2020-09-05 13:12 +0100
      Re: Bit Swizzling "John Levine" <johnl@taugh.com> - 2020-09-05 18:50 +0000
        Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-06 11:01 -0400
        Re: Bit Swizzling Chris <xxx.syseng.yyy@gfsys.co.uk> - 2020-09-06 17:48 +0100
    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

#61300 — Bit Swizzling

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

[toc] | [next] | [standalone]

#61301

On Friday, September 4, 2020 at 7:44:20 PM UTC-5, Rick C. Hodgin wrote:
> 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)

The input variable s should be a for loop inside of the swizzle function.
The input variable d should be consumed as part of running the for loop.
The constant 1 I think should be 15 or 0xF

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

The Hardware answer is that swizzle is simply a multiplexer with k inputs
of size j such that j×k = bits-in-register. With the number of bits in a
register a power of 2, K will also be a power of 2, and j a logarithm of
a power of 2.

For a 64-bit register and a byte swizzler, one needs eight 8-bit multiplexers
and eight 3-bit multiplex indexes (or a 8×3 = 24-bit constant)

The One I put in the Samsung GPU ISA used 32-bit registers and 4-bit swizzle
sizes; so we still had 8 multiplexers and the index count was still 3-bits.
The inputs could be from a constant field or from a register.

In both cases any given multiplexer produces a fixed number of bits at a
fixed position in the output. This is actually faster than a shift or
add (because the depth of the multiplexer is thinner at 2-gates of delay).

Swizzle can also be used to perform various SMEAR activities:

     0404040404040404 = SWIZZLE( 0706050403020100, 44444444 );

The problem in SW is that the native register sizes are "all wrong" so
on has to compute and paste.

unit64_t swizzle( uint64_t container, uint32_t indexer )
{
     uint64_t out = 0;
     for( uint64_t i = 0; i < 64; i += 8, indexer >>= 4 )
          out |= ((container >> (indexer & 15)) & 256) << i;
     return out;
}

[toc] | [prev] | [next] | [standalone]

#61302

On Friday, September 4, 2020 at 8:26:30 PM UTC-5, MitchAlsup wrote:
> On Friday, September 4, 2020 at 7:44:20 PM UTC-5, Rick C. Hodgin wrote:
> > 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)
> 
> The input variable s should be a for loop inside of the swizzle function.
> The input variable d should be consumed as part of running the for loop.
> The constant 1 I think should be 15 or 0xF
> 
> >      {
> >          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
> 
> The Hardware answer is that swizzle is simply a multiplexer with k inputs
> of size j such that j×k = bits-in-register. With the number of bits in a
> register a power of 2, K will also be a power of 2, and j a logarithm of
> a power of 2.
> 
> For a 64-bit register and a byte swizzler, one needs eight 8-bit multiplexers
> and eight 3-bit multiplex indexes (or a 8×3 = 24-bit constant)
> 
> The One I put in the Samsung GPU ISA used 32-bit registers and 4-bit swizzle
> sizes; so we still had 8 multiplexers and the index count was still 3-bits.
> The inputs could be from a constant field or from a register.
> 
> In both cases any given multiplexer produces a fixed number of bits at a
> fixed position in the output. This is actually faster than a shift or
> add (because the depth of the multiplexer is thinner at 2-gates of delay).
> 
> Swizzle can also be used to perform various SMEAR activities:
> 
>      0404040404040404 = SWIZZLE( 0706050403020100, 44444444 );
> 
> The problem in SW is that the native register sizes are "all wrong" so
> on has to compute and paste.
> 
> unit64_t swizzle( uint64_t container, uint32_t indexer )
> {
>      uint64_t out = 0;
>      for( uint64_t i = 0; i < 64; i += 8, indexer >>= 4 )
>           out |= ((container >> (indexer & 15)) & 256) << i;
>      return out;
> }

Make that 255 instead of 256.......

[toc] | [prev] | [next] | [standalone]

#61304

On Saturday, 5 September 2020 at 01:44:20 UTC+1, Rick C. Hodgin wrote:
> 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? 

For an 8 bit value there's a quick method.

Start with abcdefgh
PDEP to get 0000000a0000000b0000000c0000000d0000000e0000000f0000000g0000000h
Multiply by an appropriate 64 bit constant to get the values in the high bits; in your example 0x20_01_80_40_04_10_08_02
Shift down by 56.

If your value is 64 bit, you can instead do
(x >> 0) & 0x0101010101010101
(x >> 1) & 0x0101010101010101
...
(x >> 7) & 0x0101010101010101
to get your strided inputs, perform a multiplication on each to get the wanted ordering of those 8 bits,
and then PDEP each into place. The overall cost is 15 shifts, 8 ands, 8 muls, 8 PDEPs and 7 ors,
with a critical path of shift-and-mul-shift-pdep-or-or-or.

I can think of more optimal sequences for special-cases.

[toc] | [prev] | [next] | [standalone]

#61309

On 9/4/20 11:32 PM, Joshua Landau wrote:
> For an 8 bit value there's a quick method.
> 
> Start with abcdefgh
> PDEP to get 0000000a0000000b0000000c0000000d0000000e0000000f0000000g0000000h
> Multiply by an appropriate 64 bit constant to get the values in the high bits; in your example 0x20_01_80_40_04_10_08_02
> Shift down by 56.

That's a good one when parallel ops are available.  Fast, and it doesn't
require much overhead.  I like it.

> If your value is 64 bit, you can instead do
> (x >> 0) & 0x0101010101010101
> (x >> 1) & 0x0101010101010101
> ...
> (x >> 7) & 0x0101010101010101
> to get your strided inputs, perform a multiplication on each to get the wanted ordering of those 8 bits,
> and then PDEP each into place. The overall cost is 15 shifts, 8 ands, 8 muls, 8 PDEPs and 7 ors,
> with a critical path of shift-and-mul-shift-pdep-or-or-or.
> 
> I can think of more optimal sequences for special-cases.

For an optimal software algorithm where only logical bitwise operators
are available on 8-bit, 16-bit, 32-bit, or 64-bit quantities, I'm going
to have to brute-force the logic through using bit identifiers in bytes,
and then do an analysis to see if any sequences exist in the destination
which match the source, and then extract out those components and
iteratively resolve down until the operation is exhausted with other
manual steps.

I was hoping this was a solved problem that is well-known with easy-to-
read C code taught in CS 351 or something where I could garner and
adapt their well-documented code. :-)

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#61307

On 05/09/2020 01:33, 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

If it's just 8-bit bytes, then it's easy: use any method to build a map 
that translates one 8-bit value to its swizzled version. I assume it 
will be used many millions of times.

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

It took me a while to figure out what this means, which appears to be 
take bit s of v, and store it as bit d of o. (But o has to start at 0 
since |= means it can't change a 1 in o to 0.)

In my language it would be simply this:

    o.[d] := v.[s]

although there, it can write both 1s and 0s into o.

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

The algorithm that works on what, bits of C++ code? What is its input? 
What are the aims: to make it fast? Will the mapping always be known 
constants, or variables? Will all bits be translated or just some?

And, what would be its output?

If it's just reordering the bits in a word (where you don't map, for 
example, both bits 5 and 7 to bit 3), that doesn't sound too hard 
(although it probably is!). But importantly, this isn't done in-place.

Up to 8 or 16 bits, probably you can use tables, but the tables need to 
be set up.

Otherwise the simplest thing I can think of, for an N-bit word, is a 
table of translation pairs. For your 8-bit example this will just be the 
parameters to your swizzle function, but as data:

   (0,6)
   (1,0)
   (2,3)
   (3,1)
   (4,2)
   (5,7)
   (6,4)
   (7,5)

This be input to a routine that will do the job, or it can be the input 
to an algorithem that generates, for example, one giant logical expression.

I can probably just about do that last part, if it doesn't need to be 
optimised, example:

   y = ((x&1)<<6)|((x&2)>>1)|((x&4)<<1)|((x&8)>>2)|
       ((x&16)>>2)|((x&32)<<2)|((x&64)>>2)|((x&128)>>2);

where x is the input word, and y is the output word. I did this with a 
12-line script based on that data input. (Not tested; may need extra 
parens.)

I'm sure gcc-O3 will find some optimisations in there if there are any.

[toc] | [prev] | [next] | [standalone]

#61308

On 09/05/20 01:33, Rick C. Hodgin wrote:
>
> 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.
>

Why not just use a lookup table ?. Minimum ops and fast...

Chris

[toc] | [prev] | [next] | [standalone]

#61312

In article <rivvah$1neg$2@gioia.aioe.org>,
>> -----
>> 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?

>Why not just use a lookup table ?. Minimum ops and fast...

Assuming you're looking for something you can implement in logic
rather than by table lookup, it sounds like a set of Karnaugh maps.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

[toc] | [prev] | [next] | [standalone]

#61318

On 9/5/20 2:50 PM, John Levine wrote:
 > Assuming you're looking for something you can implement in logic
 > rather than by table lookup...

Correct.

I'm looking for an algorithm to analyze bit swizzling requirements and
generate optimal code for them given the capabilities and constraints of
various ISAs.

 > it sounds like a set of Karnaugh maps

This is part of my CAlive project.  I'm looking for an algorithm which
already has the logic worked out, rather than (re-)inventing myself.

Note:  I originally cross-posted this to comp.compilers yesterday, but
        John Levine did not allow it to post.  I reply here only to the
        other group he cross-posted to originally, comp.arch.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#61321

On 09/05/20 19:50, John Levine wrote:
> In article<rivvah$1neg$2@gioia.aioe.org>,
>>> -----
>>> 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?
>
>> Why not just use a lookup table ?. Minimum ops and fast...
>
> Assuming you're looking for something you can implement in logic
> rather than by table lookup, it sounds like a set of Karnaugh maps.

Unless this is just an intellectual exercise for the fun of it, an
engineer would choose the minimal design at lowest cost to
satisfy the requirements. Table methods don't have to be in
software as a single eprom or gate array could do it in hardware.
8 inputs to address lines, then 8 bits of output, scale as required,
so why make life more difficult than necessary ?.

Old project here, where a programmer spent nearly 5 pages of 6800
asm to translate an input connect pin layout to that required for
the internal functions. Code was impenetrable, so substituted a
256 byte lookup table. Less space that the code and easily
modified for new requirements...

Chris
[I think the question is whether there is a way to mechanically
generate a version of the opaque assembler. -John]

[toc] | [prev] | [next] | [standalone]

#61342

On 9/4/2020 7:33 PM, Rick C. Hodgin wrote:
> 
> 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.
> 

https://www.techopedia.com/definition/22413/swizzling

-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [next] | [standalone]

#61343

On 9/8/2020 11:25 AM, olcott wrote:
> On 9/4/2020 7:33 PM, Rick C. Hodgin wrote:
>>
>> 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.
>>
> 
> https://www.techopedia.com/definition/22413/swizzling
> 


glTexParameteri(Target, GL_TEXTURE_SWIZZLE_R, Format.Swizzle[0]);
glTexParameteri(Target, GL_TEXTURE_SWIZZLE_G, Format.Swizzle[1]);
glTexParameteri(Target, GL_TEXTURE_SWIZZLE_B, Format.Swizzle[2]);
glTexParameteri(Target, GL_TEXTURE_SWIZZLE_A, Format.Swizzle[3]);
https://gli.g-truc.net/0.7.0/index.html

-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [standalone]

Back to top | Article view | comp.arch

csiph-web