c - Fast method to copy memory with translation - ARGB to BGR

Question

Overview

I have an image buffer that I need to convert to another format. The origin image buffer is four channels, 8 bits per channel, Alpha, Red, Green, and Blue. The destination buffer is three channels, 8 bits per channel, Blue, Green, and Red.

So the brute force method is:

// Assume a 32 x 32 pixel image
#define IMAGESIZE (32*32)

typedef struct{ UInt8 Alpha; UInt8 Red; UInt8 Green; UInt8 Blue; } ARGB;
typedef struct{ UInt8 Blue; UInt8 Green; UInt8 Red; } BGR;

ARGB orig[IMAGESIZE];
BGR  dest[IMAGESIZE];

for(x = 0; x < IMAGESIZE; x++)
{
     dest[x].Red = orig[x].Red;
     dest[x].Green = orig[x].Green;
     dest[x].Blue = orig[x].Blue;
}

However, I need more speed than is provided by a loop and three byte copies. I'm hoping there might be a few tricks I can use to reduce the number of memory reads and writes, given that I'm running on a 32 bit machine.

Additional info

Every image is a multiple of at least 4 pixels. So we could address 16 ARGB bytes and move them into 12 RGB bytes per loop. Perhaps this fact can be used to speed things up, especially as it falls nicely into 32 bit boundaries.

I have access to OpenCL - and while that requires moving the entire buffer into the GPU memory, then moving the result back out, the fact that OpenCL can work on many portions of the image simultaneously, and the fact that large memory block moves are actually quite efficient may make this a worthwhile exploration.

While I've given the example of small buffers above, I really am moving HD video (1920x1080) and sometimes larger, mostly smaller, buffers around, so while a 32x32 situation may be trivial, copying 8.3MB of image data byte by byte is really, really bad.

Running on Intel processors (Core 2 and above) and thus there are streaming and data processing commands I'm aware exist, but don't know about - perhaps pointers on where to look for specialized data handling instructions would be good.

This is going into an OS X application, and I'm using XCode 4. If assembly is painless and the obvious way to go, I'm fine traveling down that path, but not having done it on this setup before makes me wary of sinking too much time into it.

Pseudo-code is fine - I'm not looking for a complete solution, just the algorithm and an explanation of any trickery that might not be immediately clear.

Answer 1

I wrote 4 different versions which work by swapping bytes. I compiled them using gcc 4.2.1 with -O3 -mssse3, ran them 10 times over 32MB of random data and found the averages.

---

Editor's note: the original inline asm used unsafe constraints, e.g. modifying input-only operands, and not telling the compiler about the side effect on memory pointed-to by pointer inputs in registers. Apparently this worked ok for the benchmark. I fixed the constraints to be properly safe for all callers. This should not affect benchmark numbers, only make sure the surrounding code is safe for all callers. Modern CPUs with higher memory bandwidth should see a bigger speedup for SIMD over 4-byte-at-a-time scalar, but the biggest benefits are when data is hot in cache (work in smaller blocks, or on smaller total sizes).

In 2020, your best bet is to use the portable _mm_loadu_si128 intrinsics version that will compile to an equivalent asm loop: https://gcc.gnu.org/wiki/DontUseInlineAsm.

Also note that all of these over-write 1 (scalar) or 4 (SIMD) bytes past the end of the output, so do the last 3 bytes separately if that's a problem.

--- @PeterCordes

---

The first version uses a C loop to convert each pixel separately, using the OSSwapInt32 function (which compiles to a bswap instruction with -O3).

void swap1(ARGB *orig, BGR *dest, unsigned imageSize) {
    unsigned x;
    for(x = 0; x < imageSize; x++) {
        *((uint32_t*)(((uint8_t*)dest)+x*3)) = OSSwapInt32(((uint32_t*)orig)[x]);
        // warning: strict-aliasing UB.  Use memcpy for unaligned loads/stores
    }
}

The second method performs the same operation, but uses an inline assembly loop instead of a C loop.

void swap2(ARGB *orig, BGR *dest, unsigned imageSize) {
    asm volatile ( // has to be volatile because the output is a side effect on pointed-to memory
        "0:
"                   // do {
        "movl   (%1),%%eax
"
        "bswapl %%eax
"
        "movl   %%eax,(%0)
"    // copy a dword byte-reversed
        "add    $4,%1
"         // orig += 4 bytes
        "add    $3,%0
"         // dest += 3 bytes
        "dec    %2
"
        "jnz    0b"                // }while(--imageSize)
        : "+r" (dest), "+r" (orig), "+r" (imageSize)
        : // no pure inputs; the asm modifies and dereferences the inputs to use them as read/write outputs.
        : "flags", "eax", "memory"
    );
}

The third version is a modified version of just a poseur's answer. I converted the built-in functions to the GCC equivalents and used the lddqu built-in function so that the input argument doesn't need to be aligned. (Editor's note: only P4 ever benefited from lddqu; it's fine to use movdqu but there's no downside.)

typedef char v16qi __attribute__ ((vector_size (16)));
void swap3(uint8_t *orig, uint8_t *dest, size_t imagesize) {
    v16qi mask = {3,2,1,7,6,5,11,10,9,15,14,13,0xFF,0xFF,0xFF,0XFF};
    uint8_t *end = orig + imagesize * 4;
    for (; orig != end; orig += 16, dest += 12) {
        __builtin_ia32_storedqu(dest,__builtin_ia32_pshufb128(__builtin_ia32_lddqu(orig),mask));
    }
}

Finally, the fourth version is the inline assembly equivalent of the third.

void swap2_2(uint8_t *orig, uint8_t *dest, size_t imagesize) {
    static const int8_t mask[16] = {3,2,1,7,6,5,11,10,9,15,14,13,0xFF,0xFF,0xFF,0XFF};
    asm volatile (
        "lddqu  %3,%%xmm1
"
        "0:
"
        "lddqu  (%1),%%xmm0
"
        "pshufb %%xmm1,%%xmm0
"
        "movdqu %%xmm0,(%0)
"
        "add    $16,%1
"
        "add    $12,%0
"
        "sub    $4,%2
"
        "jnz    0b"
        : "+r" (dest), "+r" (orig), "+r" (imagesize)
        : "m" (mask)  // whole array as a memory operand.  "x" would get the compiler to load it
        : "flags", "xmm0", "xmm1", "memory"
    );
}

(These all compile fine with GCC9.3, but clang10 doesn't know __builtin_ia32_pshufb128; use _mm_shuffle_epi8.)

On my 2010 MacBook Pro, 2.4 Ghz i5 (Westmere/Arrandale), 4GB RAM, these were the average times for each:

Version 1: 10.8630 milliseconds
Version 2: 11.3254 milliseconds
Version 3:  9.3163 milliseconds
Version 4:  9.3584 milliseconds

As you can see, the compiler is good enough at optimization that you don't need to write assembly. Also, the vector functions were only 1.5 milliseconds faster on 32MB of data, so it won't cause much harm if you want to support the earliest Intel macs, which didn't support SSSE3.

Edit: liori asked for standard deviation information. Unfortunately, I hadn't saved the data points, so I ran another test with 25 iterations.

              Average    | Standard Deviation
Brute force: 18.01956 ms | 1.22980 ms (6.8%)
Version 1:   11.13120 ms | 0.81076 ms (7.3%)
Version 2:   11.27092 ms | 0.66209 ms (5.9%)
Version 3:    9.29184 ms | 0.27851 ms (3.0%)
Version 4:    9.40948 ms | 0.32702 ms (3.5%)

Also, here is the raw data from the new tests, in case anyone wants it. For each iteration, a 32MB data set was randomly generated and run through the four functions. The runtime of each function in microseconds is listed below.

Brute force: 22173 18344 17458 17277 17508 19844 17093 17116 19758 17395 18393 17075 17499 19023 19875 17203 16996 17442 17458 17073 17043 18567 17285 17746 17845
Version 1:   10508 11042 13432 11892 12577 10587 11281 11912 12500 10601 10551 10444 11655 10421 11285 10554 10334 10452 10490 10554 10419 11458 11682 11048 10601
Version 2:   10623 12797 13173 11130 11218 11433 11621 10793 11026 10635 11042 11328 12782 10943 10693 10755 11547 11028 10972 10811 11152 11143 11240 10952 10936
Version 3:    9036  9619  9341  8970  9453  9758  9043 10114  9243  9027  9163  9176  9168  9122  9514  9049  9161  9086  9064  9604  9178  9233  9301  9717  9156
Version 4:    9339 10119  9846  9217  9526  9182  9145 10286  9051  9614  9249  9653  9799  9270  9173  9103  9132  9550  9147  9157  9199  9113  9699  9354  9314