Fastest way to copy memory with stride in C?

Question

I'm trying to copy 1 or 2 colour channels from RGBA image data as quickly as possible (this is the slowest part of my code, and it's slowing the whole app down). Is there a fast way of copying with stride?

The data is simply laid out as RGBARGBARGBA etc., and I need to copy just the R values, or in another case just the RG values.

What I have so far is roughly this to copy the R values:

for(int i=0; i<dataSize; i++){
    dest[i] = source[i*4];
}

For the RG values, I'm doing:

for(int i=0; i<dataSize; i+=2){
    dest[i] = source[i*2];
    dest[i+1] = source[(i*2)+1];
}

All the data is unsigned 1-byte values. Is there a faster way? I've already partially unrolled the loop (doing 64 values per iteration - insignificant speedup beyond that). Platform is Armv7 (iOS), so using NEON (SIMD) might be useful, I've zero experience with that unfortunately!

Changing the data is unfortunately out of the question, it's provided by opengl's readPixels() function, and iOS doesn't support reading as L, LA, RG etc. so far as I've been able to tell.

Answer 1

If you're OK with iOS4 and above, you might find vDSP and the accelerate framework useful. Check out the documentation for all sorts of image manipulation goodness at warp speed.

#import <Accelerate/Accelerate.h>

I don't know what you do next, but if you're doing any form of calculation on the image data, and want it in floating point form, you can use vDSP_vfltu8 to convert one channel of the source byte data to single precision floating point using a single line like this (excluding the memory management);

vDSP_vfltu8(srcData+0,4,destinationAsFloatRed,1,numberOfPixels)
vDSP_vfltu8(srcData+1,4,destinationAsFloatGreen,1,numberOfPixels)
vDSP_vfltu8(srcData+2,4,destinationAsFloatBlue,1,numberOfPixels)
vDSP_vfltu8(srcData+3,4,destinationAsFloatAlpha,1,numberOfPixels)

If you then need to create an image from the manipulated floating point data, use vDSP_vfuxu8 to go back the other way - so;

vDSP_vfixu8(destinationAsFloatRed,1,outputData+0,4,numberOfPixels);
vDSP_vfixu8(destinationAsFloatGreen,1,outputData+1,4,numberOfPixels);
vDSP_vfixu8(destinationAsFloatBlue,1,outputData+2,4,numberOfPixels);
vDSP_vfixu8(destinationAsFloatAlpha,1,outputData+3,4,numberOfPixels);

Obviously you can just process 1 or 2 channels using the above technique.

The documentation is quite complex, but the results are good.

Answer 2

As always load and store are the most expensive operations. You could optimize your code in the following fashion:

• Load one int (RGBA)
• Store the required part in a register (temp variable)
• Shift the data to the right place in the temp variable.
• Do this until the native prozessor data size is full (4 times for chars on a 32bit machine)
• store temp variable to memory.

The code is just fast typed to get the idea across.

unsigned int tmp;
unsigned int *dest;

for(int i=0; i<dataSize; i+=4){
    tmp  = (source[i] & 0xFF);
    tmp |= (source[i+1] & 0xFF) << 8;
    tmp |= (source[i+2] & 0xFF) << 16;
    tmp |= (source[i+3] & 0xFF) << 24;

    *dest++ = tmp;
}

Answer 3

Depending on the compiled code, you may want to replace the muliplication by 2 with addition of a second loop index (call it j and advance it by 4):

for(int i=0, j=0; i<dataSize; i+=2, j+=4){
    dest[$i] = source[$j];
    dest[$i+1] = source[$j+1];
}

Alternatively, you can replace the multiplication with a shift by 1:

for(int i=0, j=0; i<dataSize; i+=2, j+=4){
    dest[$i] = source[$i<<1];
    dest[$i+1] = source[($i<<1)+1];
}

Answer 4

I'm more of a while guy -- you can convert it to for, I'm sure

i = j = 0;
while (dataSize--) {
    dst[i++] = src[j++]; /* R */
    dst[i++] = src[j++]; /* G */
    j += 2;              /* ignore B and A */
}

As for it being faster, you have to measure.

Answer 5

Is your question still actual? I have published my ASM-accelerated function for copying bytes with stride some days ago. It is about twice faster than corresponding C code. You can find it here: https://github.com/noveogroup/ios-aux It can be modified to copy words in case of RG-bytes copying.

UPD: I have discovered that my solution is faster than C-code only in debug mode when compiler's optimization is switched off by default. In release mode C-code is optimized (by default) and works as fast as my ASM-code.

Answer 6

Hope I'm not too late to the party! I just accomplished something similar on the iPad using ARM NEON intrinsics. I get a 2-3x speed up compared to the other listed answers. Note that the code below keeps only the first channel and requires the data to be a multiple of 32 bytes.

uint32x4_t mask = vdupq_n_u32(0xFF);

for (unsigned int i=0, j=0; i < dataSize; i+=32, j+=8) {

    // Load eight 4-byte integers from the source
    uint32x4_t vec0 = vld1q_u32((const unsigned int *) &source[i]);
    uint32x4_t vec1 = vld1q_u32((const unsigned int *) &source[i+16]);

    // Zero everything but the first byte in each of the eight integers
    vec0 = vandq_u32(vec0, mask);
    vec1 = vandq_u32(vec1, mask);

    // Throw away two bytes for each of the original integers
    uint16x4_t vec0_s = vmovn_u32(vec0);
    uint16x4_t vec1_s = vmovn_u32(vec1);

    // Combine the remaining bytes into a single vector
    uint16x8_t vec01_s = vcombine_u16(vec0_s, vec1_s);

    // Throw away the last byte for each of the original integers
    uint8x8_t vec_o = vmovn_u16(vec01_s);

    // Store to destination
    vst1_u8(&dest[j], vec_o);
}

Answer 7

The answer from Roger is probably the cleanest solution. It's always good to have a library to keep your code small. But if you only want to optimize C code you can try different things. First you should analyze how big your dataSize is. You then can do heavy loop unrolling, probably combined with copying int's instead of bytes: (pseudo code)

while(dataSize-i > n) { // n being 10 or whatever
   *(int*)(src+i) = *(int*)(dest+i); i++; // or i+=4; depending what you copy
   *(int*)(src+i) = *(int*)(dest+i);
   ... n times
}

and then do the rest with:

switch(dataSize-i) {
    case n-1: *(src+i) = *(dest+i); i++;
    case n-2: ...
    case 1: ...
}

it gets a bit ugly.. but it sure is fast :)

you can optimize even more if you know how dataSize behaves. Maybe it's always a power of 2? Or an even number?

---

I just realized that you can't copy 4 bytes at once :) but only 2 bytes. Anyway, I just wanted to show you how to end an unrolled loop with a switch statement with only 1 comparison. IMO the only way to get a decent speedup.

Answer 8

Are you comfortable with ASM? I am not familiar with ARM processors, but on the Analog Devices' Blackfin, this copy is actually FREE, since it can be done in parallel to a compute operation:

i0 = _src_addr;
i1 = _dest_addr;
p0 = dataSize - 1;

r0 = [i0++];
loop _mycopy lc0 = p0;
loop_begin _mycopy;
    /* possibly do compute work here | */ r0 = [i0++] | W [i1++] = r0.l;
loop_end _mycopy;
W [i1++] = r0.l;

So, you have 1 cycle per pixel. Note that as-is, this is good for RG or BA copy. As I said, I am not familiar with ARM and absolutely know nothing about iOS so I am not sure you even have access to ASM code, but you can try looking for that kind of optimizations.