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)

Reply to
Rick C. Hodgin
Loading thread data ...

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.

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.

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)1)|((x&4)2)| ((x&16)>>2)|((x&32)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.

Reply to
Bart

formatting link

--
Copyright 2020 Pete Olcott
Reply to
olcott

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

formatting link

--
Copyright 2020 Pete Olcott
Reply to
olcott

(Too many xpost groups, had to remove one)

Rick,

Reply to
R.Wieser

A good compiler can sometimes (not always) do that kind of thing in the generated code, if it recognises the pattern. Often, however, these kind of small instructions are effectively free on x86 processors as you wait for memory (of course that depends very heavily on the rest of the code and how you are using this function).

Such a function would be (or should be) inlined by the compiler - using an inline function is almost always a better choice than a macro if you don't /need/ it to be a macro.

Reply to
David Brown

I appreciate your response, Rudy. I'm writing my own CAlive language, and my request for an algorithm is to have my internal intermediate language able to then generate optimum code sequences for a target ISA given the constraints of that ISA.

It's a fairly complex task which is why I reached out for it. I'm adding swizzle operator support so you can name an operator and apply inlined swizzle operation to data (as an operator and not as a func- tion call).

It was an example only of a worst-case scenario for swizzling data. I'm sorry that wasn't more clear. :-)

--
Rick C. Hodgin
Reply to
Rick C. Hodgin

Rick,

I already thought I recognised your name (and its weight around here), and by it wondered if I could tell you anything at all.

It seems to me that I concentrated on the wrong thing. Thanks for not biting my head off. :-)

Regards, Rudy Wieser

Reply to
R.Wieser

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.