The following C code demonstrates the simulated vector functionality of a logical AND upon a 128-bit vector. The code sample logical AND's the four packed 32-bit values from vector A and B, to effectively AND all 128 bits and then stores the result in vector D. Note that the function stores the result pointed to by the first function argument.

  void vmp_pand(void *pvD, void *pvA, void *pvB)
  {

    uint32 *pD, *pA, *pB;

    ASSERT_PTR16(pvD);
    ASSERT_PTR16(pvA);
    ASSERT_PTR16(pvB);

    pD=(uint32*) pvD;
    pA=(uint32*) pvA;
    pB=(uint32*) pvB;
    *(pD+0) = *(pA+0) & *(pB+0);
    *(pD+1) = *(pA+1) & *(pB+1);

    *(pD+2) = *(pA+2) & *(pB+2);
    *(pD+3) = *(pA+3) & *(pB+3);
  }

  mov    eax,pvA     ; A (Source) Vector
  mov    ebx,pvB     ; B (Source) Vector
  mov    edx,pvD     ; D (Destination) Vector

  mov     ebp,[eax+0]       ; Read A lower 64 bits
  mov     esi,[eax+4]
  mov     ecx,[ebx+0]       ; " B " "
  mov     edi,[ebx+4]
  and     ebp,ecx           ; AND bits (31...0)
  and     esi,edi           ; AND bits (63...32)
  mov     [edx+0],ebp       ; Write lower 64 bits
  mov     [edx+4],esi


  mov     ebp,[eax+8]       ; Read A upper 64 bits
  mov     esi,[eax+12]
  mov     ecx,[ebx+8]       ; " B " "
  mov     edi,[ebx+12]
  and     ebp,ecx           ; AND bits (95...64)
  and     esi,edi           ; AND bits (127...96)
  mov     [edx+8],ebp       ; Write upper 64 bits
  mov     [edx+12],esi

  mov     rax,pvA         ; A (Source) Vector
  mov     rbx,pvB         ; B (Source) Vector
  mov     rdx,pvD         ; D (Destination) Vector


  mov     r8,[rax+0]      ; Read A lower 64 bits
  mov     r9,[rax+8]      ; Read A upper 64 bits
  mov     r10,[rbx+0]     ; Read B lower 64 bits
  mov     r11,[rbx+8]     ; Read B upper 64 bits
  and     r8,r10          ; AND bits (63...0)
  and     r9,r11          ; AND bits (127...64)
  mov     [rdx+0],r8      ; Write lower 64 bits
  mov     [rdx+8],r9      ; Write upper 64 bits

  movq    mm0,[ebx+0]   ; Read B lower 64 bits
  movq    mm1,[ebx+8]   ;   "    B upper "
  movq    mm2,[eax+0]   ; Read A lower 64 bits
  movq    mm3,[eax+8]   ;   "    A upper "

  pand  mm0,mm2         ; AND lower 64 bits
  pand  mm1,mm3         ; AND upper 64 bits

  movq    [edx+0],mm0   ; Write D lower 64 bits
  movq    [edx+8],mm1   ;   "     upper   "

  movdqa     xmm0,[ebx]      ; Read B Aligned 128 bits
  movdqa     xmm1,[eax]      ; Read A

  pand       xmm0,xmm1       ; AND 128 bits

  movdqa     [edx],xmm0      ; Write D Aligned 128 bits

  movdqu    xmm0,[ebx]      ; Read B non-aligned 128 bits
  movdqu    xmm1,[eax]      ; Read A

  pand      xmm0,xmm1       ; AND 128 bits

  movdqu    [edx],xmm0      ; Write D non-aligned 128 bits

The following C code demonstrates the functionality of a logical OR upon a 128-bit vector. The code sample logical OR's the four blocks of 32-bit values from vector A and B 32 bits at a time four times to effectively OR all 128 bits, and then stores the result in vector D. Note that the function stores the result pointed to by the first function argument.

  void vmp_por(void *pvD, void *pvA, void *pvB)
  {
    uint32 *pD, *pA, *pB;
    
    pD=(uint32*) pvD;
    pA=(uint32*) pvA;
    pB=(uint32*) pvB;
    *(pD+0) = *(pA+0) | *(pB+0);   // {31...0}
    *(pD+1) = *(pA+1) | *(pB+1);   // {63...32}
    *(pD+2) = *(pA+2) | *(pB+2);   // {95...64}
    *(pD+3) = *(pA+3) | *(pB+3);   // {127...96}
  }

The following C code demonstrates the functionality of a logical XOR upon a 128-bit vector. The code sample logical XOR's the four blocks of 32-bit elements from vector A and B to effectively XOR all 128 bits and then stores the result in vector D. Note that the function stores the result referenced by the first function parameter pointer.

Logical Packed XOR D=(AB)

Example 4-8. ...chap04pboolPBool.cpp

  void vmp_pxor(void *pvD, void *pvA, void *pvB)
  {
    uint32 *pD, *pA, *pB;
    
    pD=(uint32*) pvD;
    pA=(uint32*) pvA;
    pB=(uint32*) pvB;
    *(pD+0) = *(pA+0) ^ *(pB+0);    // {31...0}
    *(pD+1) = *(pA+1) ^ *(pB+1);    // {63...32}
    *(pD+2) = *(pA+2) ^ *(pB+2);    // {95...64}
    *(pD+3) = *(pA+3) ^ *(pB+3);    // {127...96}
  }

See the code snippets from the previously discussed instruction AND, then substitute the instruction {^, xor, pxor} for the {&, and, pand} accordingly.

Another use for this operation is as a Boolean NOT (one's complement) operator. By using an input A and setting B permanently to a logical one, an inverse bit is achieved. Note the following table where zero becomes one and one becomes zero.

Figure 4-1. Example of using a logical XOR with a logical true bit to achieve the equivalent of a logical NOT condition.

As can be seen, input A and output Y are the exact opposite. Keep in mind that Boolean logic is bit based and bit isolated so that adjacent bits do not affect each other.

This instruction logically inverts the bits of the destination. All ones become zeros, and all zeros become ones.

And guess what you get when you flip it again?

The original value! Flip-flop.

This instruction logically inverts the sign of the number.

Another use for an XOR is in an implementation for a negation (two's complement). As a refresher, a subtraction is a two's complement followed by an addition. By inverting all bits, a one's complement is achieved. The next step for the two's complement is by an increment (addition of one) of this value. This is followed by the addition, which effectively results in the subtraction.

This operation is the result of a Boolean NOT (one's complement) operator that was just discussed, followed by an increment or an addition by one. Of course, this is not as slick as a reverse subtraction where...

-A = A ISUB 0     thus    -A = 0 - A

but not all processors support that. Keep in mind though, that when dealing with pipelining your code, a two-step operation may be more helpful than a single step.

An interesting use for a logical XOR is as a butterfly switch to allow for branchless coding. Branchless code is discussed in Chapter 11, but this is a good time to take a break and twiddle some bits. Normal coding that uses branching is typically taught using something as follows:

  #define FLIP  -30
  #define FLOP   47

    if (FLIP == nf)
    {
      nf = FLOP;
    }
    else
    {
      nf = FLIP;
    }

...or...

   nf = (FLIP == nf) ? FLOP : FLIP;

No matter which way you coded it, it is the same, identical code. This is fine and dandy, but the branching and especially a possible misprediction of a branch takes time and there are two branches to contend with. If in a flip, it flops, and if in a flop, it flips. Of course, instead of two branches such as the previous code snippet, it could always be coded for one branch such as follows:

nf = FLIP;
if (FLIP == nf)

{
  nf = FLOP;
}

The code, if not a FLIP as in the previous code snippet, branches around and continues on, but again, there could be a misprediction.

A misprediction is as it sounds. A more advanced CPU will predict that at an if-then conditional, it will take the branch and do the conditional or branch around, thus the if-then-else. The problem is that the CPU gains efficiency by predicting that it is correct because it is preloading memory and, in some cases, executing instructions that are further down in the code. The punishment comes that if it predicted wrong, that memory has to be thrown away and the results of the calculations it processed ahead of time disposed of. Then it needs to continue processing down the correct path. Either way, this is very time consuming, and so alternative (branchless) methods need to be devised if possible.

My favorite solution is a branchless result so there is no misprediction and the appropriate value can be selected with a butterfly switch. Let's examine these two values more closely:

FLOP    =       47      =       0x002F    =   0000000000101111b
FLIP    =      -30      =       0xFFE2    =   1111111111100010b

...and calculate the logical XOR of those two values:

FLIPPY  =      -51      =       0xFFCD    =   1111111111001101b

So if in our code initialization we preset a value:

nf  =  FLOP;

...and in place of the branching code the following snippet is used instead:

xor   nf,nf,FLIPPY   // FLIP/FLOP

...then each time the code is executed it will flip to the alternate value.

FLIP FLOP FLIP FLOP FLIP FLOP FLIP, etc.

Pretty cool, huh! And the best part is the actual code is a single instruction, not a group of instructions to process a branch and decide whether to branch or not! The code runs a lot faster, and it's smaller. This also works with non-definitions as well. Initialize with the following:

nf = valueA;            // First value
iFlipVal = nf ^ valueB; // Butterfly key

...and then select the value with the following:

nf = nf ^ iFlipVal;

... and it works great in a parallel configuration. Different butterflies to control different elements, all in parallel.

If anything, at least this book is informative!

I know this is not x86 related, but what instruction is thought to be missing from the VU coprocessor on the PS2?

The XOR!!!

This seems to be a popular interview question, as I have encountered it numerous times. Yes, I know, I digress. The 80×86 supports the XOR instruction as was discussed, but this is good practice for the other Boolean instructions that have been touched on in this chapter.

After interviewers ask this question, they then sometimes want to know how to write equivalent code. Funny thing is that they do not seem to remember the answer themselves. I will hastily draw out the following truth table from left to right, and then draw the circuit for good measure. (That is, if I am not too tired and frustrated from having to answer programming questions all day long!)

Figure 4-2. A four-gate (OR, NOT-AND, AND) solution to achieve an equivalent result of a logical XOR

I will then hesitate for a second and then announce, "But wait!" This takes four logical operations — an OR, AND, NOT, then AND. So instead let's make this a bit smaller. If ANDC type functionality is used (which has not been discussed yet)...

Figure 4-3. A two-gate (ANDC, OR) solution to achieve an equivalent result of a logical XOR

...notice the swapped inputs and the gate functionality similar to a logical AND, then the outputs are logical OR gated together. So now it is down to two!

But wait. What if there were no NOT, NOR, XOR, or ANDC instruction? At this point, if you replicate what is being presented here at your interview as a response to the question, you will either come off sounding like a really smart guy or a prima donna, depending on how you do it. So you then announce, "But wait! There is no NOT or ANDC, so how do we do it!" (Keep in mind there is a NOT and an ANDC on the 80×86.) "Ever hear of a half-adder?" It has the same result as that of an XOR except that it also contains a carry, and that is where the problem resides. That carry bit is contaminating an adjacent bit.

So if the bits are stripped into an odd-even arrangement, the A and B (odd bits) are summed, then masked with the 1010 bit mask pattern. The A and B (even bits) are summed, then masked with the 0101 even bit mask pattern. The results of the odd and even are logical OR'd with each other; effectively a logical XOR is simulated. Let's examine some 16-bit data:

So effectively all the odd bits are separated from the even bits. Odd bits are stored in a {o0o0...o0o0} bit pattern while the even bits are stored in a {0e0e...0e0e} bit pattern. So by a logical AND with the odd {10} and even {01} binary masks, an un-interlaced form is generated. This allows the odd and even bits to be handled separately, and the overflow from any operation is stored in the adjacent (next higher) bit. This means any carry will be ignored when the odd and even results are blended back together. The carry results will be removed using the same odd or even mask. Notice the bits indicated in bold are the usable result from the AND.

Now the even and odd values of A and B are summed up separately. Note that we only care about the resulting bits in bold and not the others, as those are the individual carries, which are stripped by the logical AND of the original mask.

Now logical OR the even bits and odd bits back together for the interlaced XOR result.

And when compared to the expected results of a "real" XOR:

        AB      1010101001010101b       0aa55h

...exactly the same. Okay, okay, a lot more operations, but just another technique for your repertoire. But now that you have special insight into the problem, here is the start of solving this equation for yourself!

You did not think that I would be giving you all the answers, did you?

The following C code demonstrates the functionality of a logical ANDC upon a 128-bit vector. The code sample logical NOT's the bits from vector B, then AND's these bits with vector A, 32 bits at a time, four times, to effectively ANDC all 128 bits, and then stores the result in vector D. Note that the function stores the result referenced by the first function parameter pointer.

  void vmp_pandc(void *pvD, void *pvA, void *pvB)
  {
    uint32 *pD, *pA, *pB;
    
    pD=(uint32*) pvD;
    pA=(uint32*) pvA;
    pB=(uint32*) pvB;
    
    *(pD+0) = (0xffffffff ^ *(pB+0)) & *(pA+0);
    *(pD+1) = (0xffffffff ^ *(pB+1)) & *(pA+1);
    *(pD+2) = (0xffffffff ^ *(pB+2)) & *(pA+2);
    *(pD+3) = (0xffffffff ^ *(pB+3)) & *(pA+3);
  }