Fastest way to draw a vertical line

[CrazyNorman]

I've been playing with drawing a vertical line quickly to an SDL Surface.
You access a specific pixel in an SDL surface by doing the following:

((unsigned int*)surface->pixels)[x + y*surface->pitch/4] = color;

To draw a vertical line, I came up with the following code:

void draw_vl(SDL_Surface * surface, int x, int y, int height, unsigned int color)
{
  unsigned int res = surface->pitch/4;
  unsigned int* fp, *cp = ((unsigned int*)surface->pixels) + x + y*res;

  for (fp = cp + height*res; cp <  fp; cp += res)
  {
    *cp = color;
  }
}

It seems fast, and I haven't been able to improve upon it. The thing is, after each *cp = color, we need to jump, etc., which from what I've heard is rather expensive CPUtime wise.

I was thinking with a fixed maximum possible height, you could do something similar to the following (semi-pseudocode):

goto RATE_START + y*INSTRUCTIONS_PER_ITERATION

RATE_START:
*cp = color;
cp += res;
*cp = color;
cp += res;
*cp = color;
... Repeat 480 times (480 pixel tall image)

This would remove any comparison checks (if cp < fp), and all jumps except one. I could use some sort of code generator, but I'm wondering if there is a cleaner way of doing this, or a simpler way of drawing lines that is faster than my current method?

What is the fastest way to draw a vertical line?

[dwks]

You could always use/look at the source for SDL_gfx or SGE (search for them under the libraries section of libsdl.org).

The way you have described sounds like a variation of Duff's Device, "spagetti code at its worst".

[CrazyNorman]

Thanks. SDL_gfx implements the vertical line function in pretty much the same way that I do (their function does boundary checking and various color checks, but the main section is the same). Duff's Device, as evil as it seems, looks like it could work. I'll test it out later and let you guys know if I manage to get it to work.

[VirtualAce]

void draw_vl(SDL_Surface * surface, int iPitch,int x, int y, int height, unsigned int color)
{
  SETUP:
  __asm {
    push esi
    mov  esi,[surface]
    
    mov eax,y
    mov ebx,iPitch
    shr ebx,2
    mul eax
    add eax,x
    add esi,eax
  
    mov eax,color
    xor   ecx,ecx
    
   }
   PLOTPIXEL:
   asm __ {
    stosd
    inc ecx
    cmp ecx,height
    jb PLOTPIXEL

    pop esi
  }
}

No guarantees its faster. Besides I don't think drawing vertical lines is a bottleneck in the first place.

[MWAAAHAAA]

Why do you want to optimize your line drawing routine? Is it a bottle neck in your code?

As to Bubba's code, why do you compare with ecx? There are specialized instructions for performing a loop, such as 'loop' or the 'rep' prefix. At the least I'd suggest doing the following:

void draw_vl(SDL_Surface * surface, int iPitch,int x, int y, int height, unsigned int color)
{
SETUP:
__asm {
push esi
mov esi,[surface]

mov eax,y
mov ebx,iPitch
shr ebx,2
mul eax
add eax,x
add esi,eax

mov eax,color
mov ecx, height

}
PLOTPIXEL:
asm __ {
rep stosd

pop esi
}
}

Even then it's no guarantee that this code will run faster, as you'd have to consider such things as pipelining of instructions.

My advice to CrazyNorman, just stick with your for loop, no point introducing needless bugs, without a good reason.

[VirtualAce]

Just a matter of style. Neither method takes less or more cycles.

[jafet]

Make sure your line drawing code is a real bottleneck first. You should profile the overall drawing code and check if this line drawing really takes up a substantial amount of time. Try turning on various optimizations and see how it goes; compilers have a notorious reputation for being able to optimize code much better than their human inventors (as they usually know the machine better). Just write straight code and expect your compiler to do its job well.

Your second version looks even worse. If it is really faster on a particular machine, using suitable optimization switches (eg. funroll-loops on gcc) will make the compiler generate that same code (only for fixed-length unrollable loops of course). If it's slower on some machine (caches, pipelines, swap, whatever other factors can cause this) then the machine's compiler will just implement a straight loop. This is what compiler languages are really for, man -- abstraction.

[Salem]

Well said jafet.