Suppose we're trying to render truetype fonts to bitmaps without<br>calling malloc().

makeCharacterBitmap() performs rasterization.

makeCharacterBitmapMemoryNeeded() computes how much temp memory to pass in.

How do we implement the latter function? Well, we have many needs for memory,<br>but the very last one we'll need is for the edge list during rasterization.<br>This depends on the number of simultaneous edges on a single scanline. This<br>depends on the character. (99% of users will never see more than 100, or maybe<br>even 10 or 20, but a font COULD have anything in it.) Specifically, it depends<br>on the edge list, which means we'll need enough temp memory to build the edge<br>list already.

We won't have memory to store the active edge list, so computing how big the<br>active edge list *would be* probably requires heroic programming, or maybe<br>unavoidably takes a significant performance hit as we have to rescan the edge<br>list. (Possibly even with heroic programming it's impossible to avoid O(N^2)<br>performance if you can't have another data structure.)

So the client will have to pass in to makeCharacterBitmapMemoryNeeded() enough<br>memory to have computed the edge list. So how much memory is that?

makeCharacterBitmapMemoryNeededMemoryNeeded() will compute the memory needed<br>for the above function.

How do we implement this? Well, we need to get the tesselated edge list. How<br>big is the tesselated edge list? How do we build the tesselated edge list?

The way this works in stb_truetype is first we build a list of all the curves<br>in the shape, and then we tesselate it. If we stick with that approach, then<br>this function still needs to build that list of curves. So we need memory to<br>store those curves, so we need

makeCharacterBitmapMemoryNeededMemoryNeededMemoryNeeded()

Of course you could directly compute the count of tesselated edges from each<br>curves without building up the full lists of curves explicitly. This does not<br>require heroic programming, but it does cost you some performance. That's<br>because truetype doesn't store coordinates as (x,y) pairs. Instead, for a given<br>shape, it stores all of the x coordinates, and then all of the y coordinates,<br>each varying length. So if you want to visit all the curves without storing<br>them, you have to fully parse all the x coordinates to find the start of the<br>y coordinates, and then start over and simultaneously parse out the x coordinates<br>and the y coordinates. Except it's more complicated than that; first there's an<br>array of N flags, then N x coords, then N y coords, where the flags control how<br>you decode the x & y coords.

This isn't a *huge* performance suck, especially since each of the other functions<br>above are also going to redo this decoding too, but it's still means writing the<br>code in a much uglier way for doing this pass.

So, for the naivest approach (without changing anything in stb_truetype), we'd<br>require:

makeCharacterBitmapMemoryNeededMemoryNeededMemoryNeeded()<br>makeCharacterBitmapMemoryNeededMemoryNeeded()<br>makeCharacterBitmapMemoryNeeded()<br>makeCharacterBitmap()

With varying amounts of rewriting of the functions, we could reduce the number<br>of these that are needed. We can even avoid the active edge list mess by simply<br>requiring the client to pass in the max # of edges on a single scanline to<br>makeCharacterBitmapMemoryNeeded() and use that to size the memory (and the burden<br>is on the client to set that correctly).

But what is all that programming in service of?

You, the client, are either going to pass in some pre-allocated<br>memory buffer of fixed size (or, conceptually, a correctly-sized<br>portion of that), or you're going to call malloc and return that<br>to us.

And then internally, our library is going to take the temporary<br>memory you pass in and make an arena and suballocate from it.<br>Except wait, our library doesn't actually need all that memory<br>at the same time. We'll have freed up the curve list by the time<br>we have the active edge list, so those can come from the same<br>memory. So, if we want to *minimize* memory usage, we actually<br>need to use a dynamic allocator internally. So, whether you call<br>malloc or use a fixed-memory block, we're going to internally<br>do something equivalent to malloc.

(Actually, in this specific case, you might be able to just allocate<br>from the beginning and end of the block, growing towards the middle.)

So, in stb_truetype, rather than have to make N passes over things<br>to figure out those sizes in advance -- when you're either going<br>to pass in an *independently-sized fixed-size reserved block*, or<br>just going to call malloc, we just say "hey, you can either let<br>us call malloc, or you can make your own little system to 'malloc'<br>out of your temporary block and pass that to us". That keeps our<br>performance *higher*, and *induces exactly the same amount of<br>fragmentation it would have* (i.e. none, because it's fragmenting<br>this temp memory that we don't care about). It just pushes the<br>complexity onto you.

[[<br>This is clearer with other types of libraries,...