My blit function for my own graphics library

Question

Here is a blit function for a graphics library I made.

I've built a small graphics library that uses an palette-indexed spritesheet to hold all of the game's sprites. The blit function copies parts of the spritesheet into the screen buffer, according to the sprite position on the screen.

Everything works very well, and it seems to be optimized quite well by the compiler, as it uses a lot of vectorized instructions, but I'm wondering if there is a way to make it more efficient.

Here is the code of the function, alongside the code of the data structures.

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct ScreenManager ScreenManager;
struct ScreenManager
{
  uint8_t* screen;
  size_t screen_width;
  size_t screen_height;
  uint32_t* buffer;
  void* sdl_window;
  void* sdl_renderer;
  void* sdl_texture;
  const uint32_t* palette;
};

typedef struct SpritesheetSlice SpritesheetSlice;
struct SpritesheetSlice
{
  size_t x;
  size_t y;
  size_t width;
  size_t height;
};

typedef struct Sprite Sprite;
struct Sprite
{
  double x;
  double y;
  SpritesheetSlice* sss;
  bool visible;
  bool allocated;
};

typedef struct SpriteManager SpriteManager;
struct SpriteManager
{
  const uint8_t* spritesheet;
  size_t spritesheet_width;
  size_t spritesheet_height;
  uint8_t* mask;
  Sprite* sprites;
  size_t sprites_maximum;
  size_t sprites_free;
};

void
blit(ScreenManager* screen_manager, SpriteManager* sprite_manager)
{
  for (size_t i = 0; i < sprite_manager->sprites_maximum; ++i)
    {
      if (sprite_manager->sprites[i].allocated)
        {
          size_t sprite_position_x = sprite_manager->sprites[i].x;
          size_t sprite_position_y = sprite_manager->sprites[i].y;

          size_t sss_offset_x = sprite_manager->sprites[i].sss->x;
          size_t sss_offset_y = sprite_manager->sprites[i].sss->y;
          size_t sss_width = sprite_manager->sprites[i].sss->width;
          size_t sss_height = sprite_manager->sprites[i].sss->height;

          size_t screen_height = screen_manager->screen_height;
          size_t screen_width = screen_manager->screen_width;
          size_t screen_size = screen_height * screen_width;

          size_t scanline_in_index = sprite_manager->spritesheet_width * sss_offset_y + sss_offset_x;
          const uint8_t* scanline_in = sprite_manager->spritesheet;

          size_t scanline_out_index = screen_width * sprite_position_y + sprite_position_x;
          uint8_t* scanline_out = screen_manager->screen;

          if (screen_width - sprite_position_x < sss_width)
            {
              sss_width = screen_width - sprite_position_x;
            }

          for (size_t y = 0; y < sss_height; ++y)
            {
              for (size_t x = 0; x < sss_width; ++x)
                {
                  uint8_t pixel = scanline_in[x + scanline_in_index];
                  if (pixel && scanline_out_index <= screen_size)
                    {
                      scanline_out[x + scanline_out_index] = pixel;
                    }
                }
              scanline_in_index += sprite_manager->spritesheet_width;
              scanline_out_index += screen_width;
            }
        }
    }
  return;
}

Answer 1

it seems to be optimized quite well by the compiler, as it uses a lot of vectorized instructions

Well, kind of. GCC didn't use vectorization at all, and Clang used some of it but in a very strange way. Let's look at what it's doing. Basically I'm reviewing what Clang did, not so much your code.. but that then informs you about your code by proxy. I'll go into what to do about it too.

Snippet 1:

    vpaddq  xmm0, xmm1, xmm6
    vpaddq  xmm1, xmm8, xmm6
    vinsertf128     ymm8, ymm1, xmm0, 1
    vpaddq  xmm0, xmm4, xmm6
    vpaddq  xmm1, xmm9, xmm6
    vinsertf128     ymm9, ymm1, xmm0, 1
    vpaddq  xmm0, xmm13, xmm6
    vpaddq  xmm1, xmm10, xmm6
    vinsertf128     ymm10, ymm1, xmm0, 1
    vpaddq  xmm0, xmm14, xmm6
    vpaddq  xmm1, xmm11, xmm6
    vinsertf128     ymm11, ymm1, xmm0, 1

The weird mix of 128bit and 256bit is due to Ivy Bridge supporting AVX but not AVX2, it's not really good to do this (usually it's better to just use 128bit SIMD and forget about 256bit unless it's floats), but it's understandable that a compiler would solve the puzzle that way.

Anyway what's happening here is that SIMD is used to .. increment x. That's not necessarily bad, but worrying, because x really doesn't need to be a vector here (in other contexts it would have made sense).

Snippet 2:

    vmovdqu xmm2, xmmword ptr [r13 + r14]
    vpcmpeqb        xmm3, xmm2, xmm5
    vextractf128    xmm12, ymm7, 1
    vextractf128    xmm1, ymm8, 1
    vpaddq  xmm0, xmm12, xmm1
    vpaddq  xmm4, xmm8, xmm7
    vinsertf128     ymm4, ymm4, xmm0, 1

Here SIMD is used to load the pixels (fine), and evaluate the condition, and evaluate x + scanline_out_index. This is fine.

Snippet 3: times a dozen

    vpextrb eax, xmm3, 1
    not     al
    test    al, 1
    je      .LBB0_17
    vpextrq rax, xmm4, 1
    vpextrb byte ptr [rcx + rax], xmm2, 1

This is not vectorized code. It's extracting scalars from the vectors, and doing a scalar test/branch, and scalar store-byte. This is not good. The whole setup of computing things in vectors is ruined by this part of the code.

I can't blame the compiler too much for this. Vectorizing a conditional store by using a blend is just illegal for compilers (it can introduce race conditions in multi-threaded code), and there is no good byte-granular conditional store in AVX (there is one for dwords, and maskmovdqu is byte-granular but is slow due the NT-hint). As the programmer, you can use a blend, and that's the only way to make it fast.

Going outside the screen with blends may not be safe, depending on how much padding it has. In any case it complicates the condition, since it doesn't have the same element size as the pixels. It would cost a lot of code to do that .. similar to what Clang did actually, plus some packs to reduce the width of the mask to byte size. Anyway I'm going to recommend keeping that condition as a branch (not one branch per pixel, that wouldn't even be possible with SIMD, but a branch to end the loop and then drop into the special handling of the chunk that got "cut in half" by the edge of the screen). You can handle the last chunk of every row by "stepping back" to align the end of the vector with the end of the row, overlapping a bit with the previous chunk. That works in this case because the operation we're doing can be safely done twice on the same pixel, that would have the same effect as doing it once. If I have time later and if you're interested, I may do a more elaborate sketch of how to do all this.

In conclusion, Clang vectorized the part that shouldn't have been vectorized, and didn't vectorize the part that should have been (it wasn't allowed to touch that part though, only you are).

Answer 2

There are a few things that can be lifted out of loops.

The three screen related variables, screen_height, screen_width, and screen_size, along with scanline_in and scanline_out, can be initialized before the outer i for loop.

In the main blit loop, the check for scanline_out_index <= screen_size can be moved to before the x loop (and when false, you can break out of the y loop because the rest of the sprite is off the screen.

Clipping is only minimally handled (for part of the sprite being off the right or bottom). If the sprite is partly off the left edge or top, or is entirely off the screen, you'll access incorrect scanlines and/or invalid memory addresses.

The use of some indexing in loops could be replaced by a pointer (to eliminate the index calculation), although the compiler optimizations are likely to do that for you.

Answer 3

I've modified my code according to the remarks that have been made here.

Changes include:

• Declaring outside of the loop variables that aren't dependent of it (see screen_height and screen_width)
• Using binary operators to get rid of the if inside the nested for loops, by using a mask, which is an array of the same dimension of the sprite sheet, to know if a pixel is transparent or no.
• Doing pointer arithmetic instead of calculating an index. I don't like to do pointer arithmetic in my code, but it does saves some instructions in the final assembly code.

Here's the code for the final function:

void
blit(ScreenManager* screen_manager, SpriteManager* sprite_manager)
{
  size_t screen_height = screen_manager->screen_height;
  size_t screen_width = screen_manager->screen_width;

  for (size_t i = 0; i < sprite_manager->sprites_maximum; ++i)
    {
      if (sprite_manager->sprites[i].allocated &&
          sprite_manager->sprites[i].visible &&
          sprite_manager->sprites[i].x <= screen_manager->screen_width &&
          sprite_manager->sprites[i].y <= screen_manager->screen_height)
        {
          size_t sprite_position_x = sprite_manager->sprites[i].x;
          size_t sprite_position_y = sprite_manager->sprites[i].y;

          size_t sss_offset_x = sprite_manager->sprites[i].sss->x;
          size_t sss_offset_y = sprite_manager->sprites[i].sss->y;
          size_t sss_width = sprite_manager->sprites[i].sss->width;
          size_t sss_height = sprite_manager->sprites[i].sss->height;

          size_t scanline_in_offset = sprite_manager->spritesheet_width * sss_offset_y + sss_offset_x;
          size_t scanline_out_offset = screen_width * sprite_position_y + sprite_position_x;

          uint8_t* scanline_in = sprite_manager->spritesheet + scanline_in_offset;
          uint8_t* scanline_out = screen_manager->screen + scanline_out_offset;
          uint8_t* mask_in = sprite_manager->mask + scanline_in_offset;

          if (sprite_position_x + sss_width > screen_width)
            {
              sss_width += screen_width - (sprite_position_x + sss_width);
            }
          if (sprite_position_y + sss_height > screen_height)
            {
              sss_height += screen_height - (sprite_position_y + sss_height);
            }

          for (size_t y = 0; y < sss_height; ++y)
            {
              for (size_t x = 0; x < sss_width; ++x)
                {
                  scanline_out[x] = (scanline_out[x] & ~mask_in[x]) | scanline_in[x];
                }
              scanline_in += sprite_manager->spritesheet_width;
              scanline_out += screen_width;
              mask_in += sprite_manager->spritesheet_width;
            }
        }
    }
}

The result assembly code, compiler for the Tiger Lake architecture, can be seen here: https://godbolt.org/z/9eWoTKTKW