ASCII Art Is Great
While the new Marathon game wasn’t the biggest success, its art style was definitely a highlight for me (even though there was some controversy surrounding even that aspect of the game). It has also rekindled my love for ASCII art and similar visual effects.
ᵂᴼᴼᶠ ႔႔
ᠸ^^ ⸝⸝
|、˜〵
じしˍ,)⁐̤ᐷ
ASCII Fox (actually it's Unicode)That is why I decided to try and write my own version of an ASCII video overlay type of effect.
My Approach
I decided to just jump into it without any research or looking at other existing solutions. That was the point of it all: to see what I can come up with.
I went for the simplest solution in everything that is not the effect itself, as not to get caught up in the small details. That’s why I decided to use FFmpeg for decoding and encoding my video frames. It has the added benefit of supporting basically every format under the sun and I can just use the command line to start it and open two pipes: one for input and one for output. Then I’d just have to apply my effect on the decoded raw bytes of the input frame and pass it to the output pipe, and let ffmpeg encode it in the format I choose.
The input frame gets decoded into a 240x135 resolution image of raw rgb24 pixel data. Then each pixel of
this frame gets turned into an 8x8 tile of pixels on the output frame, achieving a final resolution of
1920x1080. This means that – regardless of the input video’s resolution – it will get squeezed or stretched
to a 16:9 aspect ratio. This should be easy to change, but since this wasn’t the aim of the project I just
decided to go with the easiest option. I might fix it later.
I also decided to write simple, CPU only, C code. No GPU, no shaders, not even thread level parallelism on the CPU side to encode multiple images simultaneously. My thought process was: let’s see how fast we can get using just the CPU, the hardware level ILP and compiler optimizations and – most importantly – writing efficient code. If that doesn’t turn out to be fast enough, then I might consider other methods for improving performance. We cross that bridge when we get there, but only if we decide it’s the other side of the river we want to be on. Once again the goal was to just implement this effect in the most simple and straightforward way possible.
Encoding intensity as ASCII characters and more
Now I had a choice to make here. I could either take the luminance of the pixels and use that to calculate one ASCII character for each pixel in my output frame; Or I could take the individual red, green and blue channels and use those to layer three different colored ASCII characters on top of each other to simulate the original colors of the image. Both seemed like a cool effect so I decided to implement both versions.
Since we’re encoding an output video with this effect applied and not rendering it in the terminal or
anywhere where we would actually use ASCII characters for rendering, we still need a pixel representation
of the different characters. That’s why I decided to use a bitmap representation for them.
My character choices for the 16 different light intensity levels were these: <blank> . , : ; = > ? I 7 C L X Q @ M. Since in my
bitmap representation even the lightest color (M) only has 37/64 pixels filled, the dynamic range gets
squished a lot. If we don’t take into account how the other characters are also not perfectly evenly spread
on the luminosity spectrum (I tried to make sure they are as evenly distributed as possible) we can say that
the output image generated this way will be only 37/64 or ~57.8% of the brightness of the input one. That is
just what happens when you apply an effect like this, but this gave me an idea for creating an alternate set
of tiles. One that does not have characters but instead some geometric patterns where the number of filled
pixels is being evenly spread across the entire spectrum – from 0 to all 64 pixels of the tile being filled.
In the full color version of the effect, layering different red, green and blue characters will also not be able to accurately represent the colors of the original input. This is because now we have basically 8 different possible colors for a given pixel: black, red, green, blue, yellow, cyan, magenta and white. The number of different colored pixels we get after layering the primary-colored characters, depends on how these different characters overlap. This is the case for the tiles too, although there the color distortion is a lot less drastic, since I took care to try and place the pixels in a more even distribution on the tiles (while still making them have interesting patterns). It is a kind of a less efficient and worse quality dithering effect.
Some example screenshots
Some example screenshots taken from the output videos the program produced when using the video clip of this song by Noisia and Former as the input.
Monochrome using ASCII tiles
RGB color using geometric tiles
Data representation the tiles
Representing the bitmap tiles as code is an interesting problem. The obvious choice would be a bool
array of length 64 – each element representing a pixel being full or empty. Thus a bool tiles[16][64]
could represent all of our tiles. After calculating the intensity of a given pixel we can look up the
tile representing that light value and then set the corresponding 64 pixels on the output frame.
Since bool values are stored as bytes, every tile would be 64 bytes in size, 16 of those means
1024 bytes for the entire 2D array, which can definitely stay in L1 cache during the entire lifetime
of the program. That means there won’t be too much of a penalty for all of these memory accesses, but
a tile – which is accessed 64 times for each pixel of the input frame, and only 1 out of every 8 bits
is actually storing useful information – cannot be fully stored in a register… unless… the compiler
decides to make use of the SIMD extensions and registers of modern CPU architectures…
(foreshadowing)
I thought of another solution as well. Since we’re using 8x8 bitmaps, we need exactly 64 bits to store
that information. That means we can represent a tile as a single uint64_t number, and the whole tile set
as 16 of those numbers. This cuts the size of the tile set down to one-eighth of the array version. This
could also mean the compiler can generate code where it loads the chosen tile into a register once.
Then using a shl and a test instruction (both fairly simple) it can get the corresponding bit
value to set on the output image. At first this seems like a clear winner (to me at least). Smaller size,
fewer memory accesses, and simple instructions? It is probably faster than the array version, right?
(more foreshadowing)
For the curious readers, here’s the uint64_t representation of both tile sets:
static const uint64_t char_list[16] = {
0x0ULL, // ' '
0x0000000000303000ULL, // '.'
0x0000000000303060ULL, // ','
0x0030300000303000ULL, // ':'
0x0030300000303060ULL, // ';'
0x0000FC0000FC0000ULL, // '='
0x6030180C18306000ULL, // '>'
0x78CC0C1830003000ULL, // '?'
0x7830303030307800ULL, // 'I'
0xFCCC0C1830303000ULL, // '7'
0x3C66C0C0C0663C00ULL, // 'C'
0xF06060606266FE00ULL, // 'L'
0xC6C66C38386CC600ULL, // 'X'
0x78CCCCCCDC781C00ULL, // 'Q'
0x7CC6DEDEDEC07800ULL, // '@'
0xC6EEFEFED6C6C600ULL, // 'M'
};
static const uint64_t tile_list[16] = {
0x0ULL, // '0'
0x0000001818000000ULL, // '4'
0x8100001818000081ULL, // '8'
0x0060600606606000ULL, // '12'
0x00247620046E2400ULL, // '16'
0x0066661818666600ULL, // '20'
0x1866669189666618ULL, // '26'
0xAA55A2AA55A2AA55ULL, // '30'
0x49B6B649B6B649B6ULL, // '34'
0xCCEC7733CCEE3733ULL, // '38'
0xF7CAB55DBAAD53EFULL, // '42'
0x7EDBB5DFFBADDB7EULL, // '48'
0xFFDB99FFFF99DBFFULL, // '52'
0x77FFFFDD77FFFFDDULL, // '56'
0x77FFFFFF77FFFFFFULL, // '60'
0xFFFFFFFFFFFFFFFFULL, // '64'
};This got me curious if it really was faster and if so how much faster? At this point the project turned more into an experiment about gcc’s codegen and optimization techniques, rather than just implementing a cool visual effect. To find out which method is better, I decided to implement both of them and compare their performance and the assembly code they got compiled into.
What the assembly tells us
I will refer to the bool tiles[16][64] implementation as the “array version” and the uint64_t tiles[16]
version as “bitmap version” (since here truly every bit encodes information about a specific pixel).
For the comparison I decided to compare release ready builds with the highest optimization level and
other performance increasing compiler flags. Namely -O3 -march=native -flto on an AMD Ryzen 5 7600 CPU.
This resulted in everything being inlined into main and the inner loops being unrolled in both versions.
Not particularly surprising. But here’s where the similarities stop.
Bitmap version
While in this version the generated assembly turned out to be more or less what I would expect, there was still a little surprise. Here is one iteration of the innermost loop.
1570: 45 89 f2 mov %r14d,%r10d
1573: 89 ef mov %ebp,%edi
1575: 44 89 fe mov %r15d,%esi
1578: 40 88 70 02 mov %sil,0x2(%rax)
157c: 44 88 10 mov %r10b,(%rax)
157f: 8d 72 06 lea 0x6(%rdx),%esi
1582: 40 88 78 01 mov %dil,0x1(%rax)
1586: c4 e2 c9 f7 f1 shlx %rsi,%rcx,%rsi
158b: 49 85 30 test %rsi,(%r8) ; -> memory access instead of load to register
158e: 0f 85 7c 01 00 00 jne 1710 <main+0x600>This sequence repeates 8 times in succession in the generated assembly, with addresses being shifted appropriately in later occurrences. The eight unrolled iterations represent one line in the output tile so the whole sequence runs 8 times for every pixel of the input video.
The surprising part is: gcc decided to not load the 64 bit number representing the tile into %r8, instead
it stores a pointer to the tile in %r8 and uses test by accessing the memory 64 * 240 * 135 = 2 073 600 times
for every frame of the video. This is not that big of a deal because the tiles are expected to stay in the
L1 cache throughout the whole runtime of the program, so there isn’t much of a penalty for doing this instead
of using a register. Still it is very interesting to see how compilers nowadays use the cache quite generously.
Array version
This is the more interesting version of the two. Using the -march=native flag, gcc generates assembly that
makes heavy use of SIMD registers for the array implementation.
1452: c5 fa 7e 2d c6 27 00 vmovq 0x27c6(%rip),%xmm5 # 3c20 <tile_list+0x4a0>
1459: 00
145a: c5 fa 7e 25 c6 27 00 vmovq 0x27c6(%rip),%xmm4 # 3c28 <tile_list+0x4a8>
1461: 00
1462: 48 81 fd af 7b 01 00 cmp $0x17baf,%rbp
1469: c5 79 6f 2d 5f 27 00 vmovdqa 0x275f(%rip),%xmm13 # 3bd0 <tile_list+0x450>
1470: 00
1471: c5 79 6f 25 67 27 00 vmovdqa 0x2767(%rip),%xmm12 # 3be0 <tile_list+0x460>
1478: 00
1479: c5 fa 7e 1d af 27 00 vmovq 0x27af(%rip),%xmm3 # 3c30 <tile_list+0x4b0>
1480: 00
1481: c5 79 6f 1d 67 27 00 vmovdqa 0x2767(%rip),%xmm11 # 3bf0 <tile_list+0x470>
1488: 00
1489: c5 79 6f 15 6f 27 00 vmovdqa 0x276f(%rip),%xmm10 # 3c00 <tile_list+0x480>
1490: 00
1491: c5 79 6f 0d 77 27 00 vmovdqa 0x2777(%rip),%xmm9 # 3c10 <tile_list+0x490>
1498: 00
1499: 76 92 jbe 142d <main+0x31d>The assembly snippet above shows how gcc opts to store elements of the tile_list array in SIMD
registers. There’s also a cmp instruction in the middle of all this, which is only a few
instructions later followed by the corresponding conditional jump. I suspect this being an
optimization made by the compiler with an understanding of the complex speculative execution
rules of contemporary CPUs. (All these optimizations make reading and understanding
the generated assembly quite a challenge)
Storing parts of the tile_list array is done in order to access these values faster in subsequent
parts of the program. Using SIMD registers also allows the processor to compare many values at once
when deciding whether a pixel should be colored in the output or not. Here’s a snippet of the generated
assembly demonstrating these multi-value SIMD comparisons.
1703: c4 c3 41 4c d6 20 vpblendvb %xmm2,%xmm14,%xmm7,%xmm2
1709: c4 c2 79 00 fa vpshufb %xmm10,%xmm0,%xmm7
170e: c4 61 f9 6e f1 vmovq %rcx,%xmm14
1713: c5 c1 74 fe vpcmpeqb %xmm6,%xmm7,%xmm7
1717: c4 c2 79 00 c1 vpshufb %xmm9,%xmm0,%xmm0
171c: c4 c3 01 4c fe 70 vpblendvb %xmm7,%xmm14,%xmm15,%xmm7
1722: c5 f9 74 c6 vpcmpeqb %xmm6,%xmm0,%xmm0
1726: c4 c1 f9 6e f2 vmovq %r10,%xmm6
172b: c4 c1 79 d6 79 08 vmovq %xmm7,0x8(%r9)
1731: c4 e1 f9 6e fa vmovq %rdx,%xmm7
1736: c4 e3 49 4c c7 00 vpblendvb %xmm0,%xmm7,%xmm6,%xmm0
173c: c4 c1 79 d6 11 vmovq %xmm2,(%r9)
1741: c4 c1 79 d6 41 10 vmovq %xmm0,0x10(%r9)There are other parts of the assembly code using SIMD instructions, each preceded by long sections of successive move and shift instructions to fill these registers with the right set of values. Deciphering these long chains of instructions is quite a challenge but it’s not necessary for our purposes.
What we can see from the generated assembly code of these two different implementations – even without going too much into the details – is that the latter uses a lot more instructions initially to move all the data around in the appropriate way in these SIMD registers (the generated assembly is around 180 lines longer in the array case), but the comparisons also process a lot more data at once.
Looking at the assembly: there isn’t one implementation that is clearly better than the other one. So the question now becomes which one of the two is faster?
Benchmarking
I tried to run some dummy tests on the two implementations, which exclusively looked at the execution speeds of the functions transforming the individual frames. These seemed to show 10-20% better performance for the array implementation. But at this point I decided to compare the whole process of decoding, transforming and encoding a video from start to finish. This not only runs these sequences of instructions billions of times, which will be a good benchmark, but it also shows how much of an actual performance difference we can expect in real workloads when using one implementation or the other.
So I compiled two binaries with the different implementations and I benchmarked them with the same input video and same settings. Here are the results:
>>> BITMAP:
Benchmark 1: ./vid2ascii -f -r 1 -o ./output/test.mp4 ./input/former.mkv
Time (mean ± σ): 7.753 s ± 0.051 s [User: 68.812 s, System: 1.904 s]
Range (min … max): 7.665 s … 7.852 s 20 runs>>> ARRAY:
Benchmark 1: ./vid2ascii -f -r 1 -o ./output/test.mp4 ./input/former.mkv
Time (mean ± σ): 7.720 s ± 0.054 s [User: 68.469 s, System: 1.898 s]
Range (min … max): 7.633 s … 7.830 s 20 runsWell… the array version performed marginally better (~0.43% faster), but
that is such a small difference that it could have been caused by almost anything.
It’s time for some profiling.
Here’s the report I generated by running perf record -g ./vid2ascii -f -r 1 -o ./output/test.mp4 ./input/former.mkv
(a lot of lines omitted):
[...]
0.96% 0.00% vf#0:0 [unknown] [.] 0x0072616e616c7000
0.89% 0.88% vid2ascii vid2ascii [.] main
0.67% 0.67% vf#0:0 libx264.so.165 [.] x264_8_trellis_coef1
[...]I don’t even remember which implementation this was at this point, but it clearly doesn’t matter much. My code accounts for 0.89% of all the sampled CPU time of the program. The rest is basically all ffmpeg. It’s clear that trying to optimize memory access patterns or getting rid of a couple of lines of assembly by some clever trick won’t make any noticeable difference in the final runtime of the program. So what now?
Increasing performance?
The other way of increasing performance would be to introduce thread level parallelism to the code, either on the CPU side or one might even consider the GPU for such a task (but at that point writing a shader would’ve been the better choice). But would we benefit from this?
Amdahl’s law states that the upper limit of speedup a program can receive is determined by the number of available processors and the portion of the code that is parallelizable. This means, that if I had an infinite number of processors available to me and I could make my code infinitely parallel without introducing any overhead I can still only expect a ~1% speedup. The reality is probably, that if I were to try introducing any parallelism to only my code, it would actually be slower than the current single-threaded version because of all the overhead of managing threads and work distribution logic.
To make this code run faster I would need to change the way the videos are being processed by ffmpeg. Maybe parallel decoding and encoding of frames and running multiple threads applying the effect simultaneously to multiple frames? Maybe something else? Honestly this is so far out of scope of the original aim of the project, that I didn’t even bother thinking about it. And the other reason being…
Do we actually need to increase performance? No, we do not! This program processes videos at basically ffmpeg speeds (in large part thanks to the small input resolution). It doesn’t get much better than that. It could easily be used realtime on 30 fps videos. There’s no need for increasing performance. The program is perfectly usable as is.
What did we learn here?
What we’ve definitely achieved is a set of cool looking video effects you can actually use if you’d like to do so!
We have also learned, that solutions, and data representations, that might look clever at first, are not necessarily more performant on modern hardware. This is because of the many performance enhancing upgrades and extensions to CPU hardware and ISA over the years, as well as the amazing abilitiy of compilers to use these extensions to generate incredibly efficient assembly code.
Thank you for reading!