Dynamically find the edge of a rectangle

Question

I have 2 2D points that are clamped together into an array: int square[4] . These four numbers are interpreted as the definition of a rectangle with horizontal lines parallel to the X axis and vertical lines parallel to the Y axis. Then, the elements of the array determine:

• Left x coordinate
• Bottom y coordinate
• X coordinate of the right edge
• The coordinate of the upper edge Y

I defined the winding order in this enum :

 enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT }; 

The minimal, complete, testable example of my code is that I get assigned the output second array: int output[4] and input WindingOrder edge . I need to populate output as follows:

 switch(edge) { case BOTTOM: output[0] = square[0]; output[1] = square[1]; output[2] = square[2]; output[3] = square[1]; break; case RIGHT: output[0] = square[2]; output[1] = square[1]; output[2] = square[2]; output[3] = square[3]; break; case TOP: output[0] = square[2]; output[1] = square[3]; output[2] = square[0]; output[3] = square[3]; break; case LEFT: output[0] = square[0]; output[1] = square[3]; output[2] = square[0]; output[3] = square[1]; break; } 

I am not married to a specific WindingOrder organization, and I do not care about the dot order in ouptut , so if changing these parameters makes it solvable, I will not go. I want to know if I can build square indexes to assign output in a for loop without an if / case / trernary expression (in other words, using bit-mul operations)?

So, I would like int i = 0 and WindingOrder edge perform bitwise operations with them to find:

 do { output[i] = array[???]; } while(++i <= LEFT); 

EDIT:

I got a lot of answers to static arrays (which I believe is the best way to solve this problem, so I gave +1). But as a logical problem, I am curious how there would be a bit of bitwise operations to dynamically find an element of a given edge. So, for example, how this body of the function should be written using arbitrary edge and i : int getIndex(int i, int edge)

Answer 1

Is it possible to override the value of the WindingOrder parameter? If that were the case, then here is my solution, in which the encoding selection indices in the WindingOrder value were checked, then simply decoded the index selection for input[] by offsetting and masking, while the output[] tag was iterated.

[Thanks to chqrlie for building the code base]:

  #include <iostream> enum WindingOrder { // the RIGHT most 4-bits indicate the selection index from input[] to output[0] // the LEFT most 4-bits indicate the selection index from input[] to output[3] BOTTOM = 0x1210, RIGHT = 0x3212, TOP = 0x3230, LEFT = 0x3010 }; void BitwiseWind(int const *input, int *output, unsigned short edge) { for (size_t i = 0; i < 4; i++) output[i] = input[(edge >> (i*4)) & 0x000F]; // decode } int main() { enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT }; int rect[4] = { 1, 3, 4, 5 }; int output[4]; for (int i = 0; i < 4; i++) { BitwiseWind(rect, output, edges[i]); std::cout << output[0] << output[1] << output[2] << output[3] << std::endl; } return 0; } 

The general getIndex (int i, enum WindingOrder edge) will be:

 int getIndex(int i,enum WindingOrder edge) { return ((edge >> (i*4)) & 0x000F); } 

I did not count how many instructions he used, but I believe that it would be a little small. And it's really easy to understand how this works. :)

Answer 2

Here is another solution. This is a variation of the static array approach, but without the actual array: the index matrix is ​​embedded in an unsigned 32-bit integer, calculated as a constant expression. The column for the edge parameter is selected with one shift; finally, the individual indices for each element of the array are selected using a simple bit offset and masking.

This solution has several advantages:

• it's easy to understand
• he does not use tests
• it does not use a static array or any other memory location
• it is independent of the winding order and can be easily configured for any order of array components
• it does not use special C99 syntax, which may not be available in C ++.

This is as close as possible to the bitwise solution.

 #include <iostream> enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT }; void BitwiseWind(int const *input, int *output, enum WindingOrder edge) { unsigned bits = ((0x00010201 << BOTTOM * 2) | (0x02010203 << RIGHT * 2) | (0x02030003 << TOP * 2) | (0x00030001 << LEFT * 2)) >> (edge * 2); output[0] = input[(bits >> 24) & 3]; output[1] = input[(bits >> 16) & 3]; output[2] = input[(bits >> 8) & 3]; output[3] = input[(bits >> 0) & 3]; } int main() { enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT }; int rect[4] = { 1, 3, 4, 5 }; int output[4]; for (int i = 0; i < 4; i++) { BitwiseWind(rect, output, edges[i]); std::cout << output[0] << output[1] << output[2] << output[3] << std::endl; } return 0; } 

Compiling BitwiseWind for x86-64 with clang -O3 generates 21 instructions, 6 more than the version of the static array, but without a memory reference. This is a little disappointing, but I hope this can lead to fewer instructions for the ARM target, using bit field extraction operation codes. By the way, the built-in version using output[i] = array[(i+(i==winding)*2)&3]; prints 25 instructions without any transitions, and gcc -O3 does much worse: it generates a lot more code with 4 tests and transitions.

The general getIndex function below compiles only with 6 x86 :

 int getIndex(int i, int edge) { return (((0x00010201 << BOTTOM * 2) | (0x02010203 << RIGHT * 2) | (0x02030003 << TOP * 2) | (0x00030001 << LEFT * 2)) >> (edge * 2 + 24 - i * 8)) & 3; } 

Answer 3

Is there any special reason why you need to use a lot of bitwise operations? Is this a rather complicated way to solve the problem?

You seem to be very concerned about speed, for example, you do not want to use modulo because it is expensive. In this case, why not just use just a simple search and loop around? Example and ideon.

EDIT: thanks to chqrlie for input. Get an updated response accordingly.

 #include <iostream> using namespace std; enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT }; void DoWinding1(unsigned int const *const in, unsigned int *const out, const enum WindingOrder ord) { static const unsigned int order[4][4] = { [BOTTOM] = {0,1,2,1}, [RIGHT] = {2,1,2,3}, [TOP] = {2,3,0,3}, [LEFT] = {0,3,0,1} }; out[0] = in[order[ord][0]]; out[1] = in[order[ord][1]]; out[2] = in[order[ord][2]]; out[3] = in[order[ord][3]]; } int main() { unsigned int idx; unsigned int rect[4] = {1, 3, 4, 5}; unsigned int out[4] = {0}; DoWinding1(rect, out, BOTTOM); std::cout << out[0] << out[1] << out[2] << out[3] << std::endl; return 0; } 

Answer 4

This has not been verified, and there may be a small error in some details, but the general idea should work.

Copying the array to the output will use the indices {0,1,2,3} . To get a specific edge, you need to do some conversion to indexes:

  changed_pos changed_to RIGHT : {2,1,2,3} 0 2 TOP : {0,3,2,3} 1 3 LEFT : {0,1,0,3} 2 0 BOTTOM: {0,1,2,1} 3 1 

Thus, you must add 2 mod 4 for the specific position of your winding. So (for example, I said unchecked), cut off might look like this:

 for (size_t i=0; i<4; ++i) { output[i] = array[(i+(i==edge)*2)%4]; } 

If the comparison is correct, add 1*2=2 , else 0*2=0 to the index and make mod 4 to stay in range.

Your enum should look like this (but I guess you figured it out yourself):

 enum WindingOrder { RIGHT, TOP, LEFT, BOTTOM }; 

MWE :

 #include <iostream> #include <string> #include <vector> enum WindingOrder { RIGHT=0, TOP, LEFT, BOTTOM }; int main() { std::vector<int> array = {2,4,8,9}; std::vector<int> output(4); std::vector<WindingOrder> test = {LEFT,RIGHT,BOTTOM,TOP}; for (auto winding : test) { for (size_t i=0; i<4; ++i) { output[i] = array[(i+(i==winding)*2)%4]; } std::cout << "winding " << winding << ": " << output[0] << output[1] << output[2] << output[3] << std::endl; } } 

Answer 5

From the answer itself, you are close to a solution. I think you need a Carnot map , which is a universal method for most problems of Boolean algebra.

Let's pretend that

Then the elements of the array determine:

 input[0]: Left edge X coordinate input[0]: Bottom edge Y coordinate input[0]: Right edge X coordinate input[0]: Top edge Y coordinate 

I defined the winding order in this listing:

 enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT }; 

Since for-loop might look like

 for (int k = 0; k != 4; ++k) { int i = getIndex(k, edge); // calculate i from k and edge output[k] = square[i]; } 

Then input k ( output[k] ) and edge , output i ( square[i] ). And since i has 2 bits, then two logical functions are needed.

Here we use P = F1(A, B, C, D) and Q = F2(A, B, C, D) to represent logical functions in which A , B , C , D , P and Q are unit, and

 k = (A << 1) + B; edge = (C << 1) + D; i = (P << 1) + Q; 

Then what we need to do is simply derive from the given conditions two logical functions F1 and F2 .

From the case switch arguments you made, we can easily get the truth table.

 k\edge 0 1 3 2 0 0 2 0 2 1 1 1 3 3 3 1 3 1 3 2 2 2 0 0 

Then divide this into two truth tables for the two bits P and Q

 P edge 0 1 3 2 k AB\CD 00 01 11 10 0 00 0 1 0 1 1 01 0 0 1 1 3 11 0 1 0 1 2 10 1 1 0 0 Q edge 0 1 3 2 k AB\CD 00 01 11 10 0 00 0 0 0 0 1 01 1 1 1 1 3 11 1 1 1 1 2 10 0 0 0 0 

These are the Carnot cards that I mentioned at the beginning. We can easily get functions.

 F1(A, B, C, D) = A~B~C + A~CD + ~B~CD + ~ABC + ~AC~D + BC~D F2(A, B, C, D) = B 

Then the program will be

 int getIndex(int k, int edge) { int A = (k >> 1) & 1; int B = k & 1; int C = (edge >> 1) & 1; int D = edge & 1; int P = A&~B&~C | A&~C&D | ~B&~C&D | ~A&B&C | ~A&C&~D | B&C&~D; int Q = B; return (P << 1) + Q; } 

Passed verification here . Of course, you can simplify the function with XOR.

---

EDIT

Using XOR to simplify the expression can be achieved most of the time, since A^B == A~B + ~AB . But that may not be what you want. First, I think that performance varies only slightly between the Sum of Products (SoP) expression and the even more simplified version with XOR. Secondly, there is no universal method (as far as I know) to simplify the expression using XOR, so you need to rely on your own experience to do this.

There are sixteen possible logical functions of two variables, but in devices with digital logic, the simplest gate schemes implement only four of them: AND, OR and their additions (NAND and NOR). And the Carnot map is used to simplify the requirements of real-world logic, so that they can be implemented using a minimum number of logic gates.

Two common expressions are used here: the sum of products and the expressions of sum expressions. These two expressions can be implemented directly using only the logical operators AND and OR. And they can be displayed directly with the Carnot card.

Answer 6

If you define the coordinates and directions clockwise, starting on the left side,

 #define LEFT 0 #define TOP 1 #define RIGHT 2 #define BOTTOM 3 

you can use

 void edge_line(int line[4], const int rect[4], const int edge) { line[0] = rect[ edge & 2 ]; line[1] = rect[ ((edge + 3) & 2) + 1 ]; line[2] = rect[ ((edge + 1) & 2) ]; line[3] = rect[ (edge & 2) + 1 ]; } 

to copy the coordinates of the edge line (each line segment is clockwise). It looks suboptimal, but using -O2 , GCC-4.8, you get substantially

 edge_line: pushl %esi pushl %ebx movl 20(%esp), %ecx movl 16(%esp), %edx movl 12(%esp), %eax movl %ecx, %esi andl $2, %esi movl (%edx,%esi,4), %ebx movl %ebx, (%eax) leal 3(%ecx), %ebx addl $1, %ecx andl $2, %ebx andl $2, %ecx addl $1, %ebx movl (%edx,%ebx,4), %ebx movl %ebx, 4(%eax) movl (%edx,%ecx,4), %ecx movl %ecx, 8(%eax) movl 4(%edx,%esi,4), %edx movl %edx, 12(%eax) popl %ebx popl %esi ret 

but on 64-bit even better

 edge_line: movl %edx, %ecx andl $2, %ecx movslq %ecx, %rcx movl (%rsi,%rcx,4), %eax movl %eax, (%rdi) leal 3(%rdx), %eax addl $1, %edx andl $2, %edx andl $2, %eax movslq %edx, %rdx cltq movl 4(%rsi,%rax,4), %eax movl %eax, 4(%rdi) movl (%rsi,%rdx,4), %eax movl %eax, 8(%rdi) movl 4(%rsi,%rcx,4), %eax movl %eax, 12(%rdi) ret 

As you can see, there are no conditional expressions, and binary operators combine and optimize to very few instructions.

Edited to add:

If we define the getIndex(i, edge) function using three binary getIndex(i, edge) , one shift bit (right by 1), three additions and one subtraction,

 int getIndex(const int i, const int edge) { return (i & 1) + ((edge + 4 - (i & 1) + (i >> 1)) & 2); } 

with which edge_line() can be implemented as

 void edge_line(int line[4], const int rect[4], const int edge) { line[0] = rect[ getIndex(0, edge) ]; line[1] = rect[ getIndex(1, edge) ]; line[2] = rect[ getIndex(2, edge) ]; line[3] = rect[ getIndex(3, edge) ]; } 

we get the same results as before. Using GCC-4.8.4 and -O2 for AMD64 / x86-64 compiles in

 getIndex: movl %edi, %edx sarl %edi andl $1, %edx subl %edx, %esi leal 4(%rsi,%rdi), %eax andl $2, %eax addl %edx, %eax ret 

and

 getIndex: movl 4(%esp), %eax movl 8(%esp), %edx movl %eax, %ecx andl $1, %ecx subl %ecx, %edx sarl %eax leal 4(%edx,%eax), %eax andl $2, %eax addl %ecx, %eax ret 

on i686. Note that I came to the above form using a four by four result table; there are other, more rigorous ways to create it, and there may be even a more optimal form. Because of this, I seriously recommend adding a great huge comment above the function, explaining the intention, and it is preferable to also show a table of results. Sort of

 /* This function returns an array index: * 0 for left * 1 for top * 2 for right * 3 for bottom * given edge: * 0 for left * 1 for top * 2 for right * 3 for bottom * and i: * 0 for initial x * 1 for initial y * 2 for final x * 3 for final y * * The result table is * | edge * | 0 1 2 3 * ----+------- * i=0 | 0 0 2 2 * i=1 | 3 1 1 3 * i=2 | 0 2 2 0 * i=3 | 1 1 3 3 * * Apologies for the write-only code. */ 

Or something similar.

Answer 7

Lets use our target variable, which will be used to index squared : int index .

Now we will create a table of the desired index for edge compared to i , with edge by row and i by column:

  ║0│1│2│3 ═╬═╪═╪═╪═ 0║0│1│2│1 ─╫─┼─┼─┼─ 1║2│1│2│3 ─╫─┼─┼─┼─ 2║2│3│0│3 ─╫─┼─┼─┼─ 3║0│3│0│1 

This shows that the least significant bit of index always odd for odd i and even for even i s. Therefore, if we could find the most significant bit of index , we would simply or using i & 1 , and we would have our index . Therefore, let's make another table of only the most significant index bit for the same edge versus i table:

  ║0│1│2│3 ═╬═╪═╪═╪═ 0║0│0│1│0 ─╫─┼─┼─┼─ 1║1│0│1│1 ─╫─┼─┼─┼─ 2║1│1│0│1 ─╫─┼─┼─┼─ 3║0│1│0│0 

Here we can see several things:

• When i is 0 or 3 , the columns are identical depending only on edge
  • These columns are set when edge is 1 or 2
• When i is 1 or 2 , the columns are facing each other
  • These columns are set when only the edge most significant bit is set or only i most significant bit is set

So, let's start by splitting edge and i into the least significant and most significant bits:

 const int ib0 = i & 1; const int ib1 = (i & 2) >> 1; const int eb0 = edge & 1; const int eb1 = (edge & 2) >> 1; 

From here it is easy to find if there are i 0 or 3 :

 const int iXor = ib0 ^ ib1; 

For condition 0 :

 const int iXorCondition = ib1 ^ eb1; 

And condition 1 :

 const int iNXorCondition = eb0 ^ eb1; 

Now we just need to combine them with the corresponding iXor and return the low-order bit of index :

 const int index = ((iNXorCondition & ~iXor | iXorCondition & iXor) << 1) | ib0; 

Combining all this into a convenient function, we get:

 int getIndex(int i, int edge) { const int ib0 = i & 1; const int ib1 = (i & 2) >> 1; const int eb0 = edge & 1; const int eb1 = (edge & 2) >> 1; const int iXor = ib0 ^ ib1; const int iNXorCondition = eb0 ^ eb1; const int iXorCondition = ib1 ^ eb1; return ((iNXorCondition & ~iXor | iXorCondition & iXor) << 1) | ib0; } 

I wrote a test live example here .

Answer 8

What I want to know is, can I build square indexes to assign output in a for loop without an if / case / trernary statement (in other words, using bit-mull operations)?

I would like to ask you, what do you expect from this?

My opinion is that the switch-case construct will usually be completely reorganized by compiler optimization code. Best of all, IMO, leave this code alone and let the compiler do it.

There are only two conditions when Id changes this view;

• You wrote in OpenCL (and not C) and wanted to optimize the code in which the decision-branch logic can be problematic for performance.

• You wanted to use explicit encoding to vectorize SIMD. There are some special operations that can help there, but this is an encoding option that blocks you in things that might work poorly on hardware without sets of SIMD commands (or perform completely differently on different hardware). It is also worth noting that some compilers can auto-vectorize with the correct encoding.

I just see little or no advantage at all for coding these operations in any other way than switch-case for C.

Answer 9

This is the way to achieve this:

 do { output[i] = square[ (edge & 1) * ( !(i & 1) * ((edge + 1) & 2) + (i & 1) * ( (!((edge - 1)/2)&1) * i + (((edge - 1)/2)&1) * (4-i) ) ) + !(edge & 1) * ( (i & 1) * (edge + 1) + !(i & 1) * ((edge & 2) - ((edge & 2)-1) * i) ) ]; } while(++i <= LEFT); 

To help you understand, I stepped back from the code, you can obviously erase all spaces. I put the tab where I ever wanted to separate the two cases. By the way, as you can see, the calculation consists of two sections for two different cases, which are symmetrical, but I solved each case using a different algorithm so that you can see different ways of achieving results.