Other than the mask layers stuff, most of my work has been on getting Azure canvas working, passing tests, and landed in the tree. Most of the work has been done before, my contribution has been on debugging, testing, and wiring things together, and of course a few interesting edge cases. To describe the work, I'll give a little background on our graphics libraries.
Back in the day, 'all' rendering in Firefox was done using the Cairo graphics library. This was wrapped in a thin wrapper library called Thebes (Cairo is the external library which does all the work, Thebes is the internal wrapper). We would like to support different graphics libraries and we would like a more efficient wrapper layer, and so was born Azure. This is a new internal system which abstracts a lot of our drawing code. Multiple backends can be slotted into Azure, and, in turn, Azure can be used as a backend for Thebes instead of using Cairo. So, for example, our graphics stack could use Thebes on top of Azure on top of Cairo (or Skia or Direct2D, etc.). Azure has some interesting advantages over Thebes, mainly that it is a state-less API (well, except for a transform and clipping rect), Bas and roc have written some interesting blog posts about this before.
The long term plan is for Thebes to be removed, and Azure to be used directly. For now there are people implementing content rendering using Thebes on top of Azure (on top of Direct2D on Windows, Core Graphics on Mac, and Skia or Cairo elsewhere).
HTML 5 canvas uses a different rendering path from the rest of content. We actually have two canvas implementations right now, one on top of Thebes and one on top of Azure. Currently the latter is used only on Windows where Direct2D is present, and the Thebes canvas is used elsewhere. We want to remove the Thebes canvas, because having two canvas implementations is a maintenance burden and affects our DOM bindings implementation.
So, I have been working on getting Azure canvas working with both Skia and Cairo backends, the former only on Windows, the latter everywhere, with Anthony Jones. It is all about ready to land, after that, we'll let it settle for a while to ensure there are no problems, and then we can remove Thebes canvas completely. Some of the interesting bits of this work have been using Skia canvases as source for tab previews on Windows, organising different backend preferences on different platforms, and ensuring we can always fall back to a safer backend, and just getting all the complex logic in Azure canvas and the various backends right. Plus the occasional memory leak, and some interesting interactions between the layers system and Azure.
In terms of the bigger picture, this work should lead to Azure totally replacing Thebes for canvas rendering. Elsewhere, Azure is being developed into the primary backend for Thebes, so that it will be used everywhere for rendering content, rather than using Cairo directly. Then we will work to remove the Thebes layer altogether so we are rendering directly with Azure, this will be fiddly because there is Thebes code everywhere in the code base. But at the end of it all, we should have faster, more efficient code, and be able to easily plugin different graphics backends, which is a win.
Tuesday, July 24, 2012
Monday, July 16, 2012
Mask layers on the basic backend
Using mask layers on the basic backend is a bit different from the GPU backends because we don't use shaders, and instead must do a bit of a dance with Cairo. Also, the transforms are different in basic layers vs. the GPU layers (relative to user space, rather than relative to the layer's container), which means we must handle the layer transform differently.
When using basic layers, the drawing is done using Cairo, or more precisely, using Thebes our wrapper graphics library. Therefore, we do not (as on the GPU backends) use shaders to do the masking, but resort to actual mask operations. The basic idea is we draw the content un-masked, use that as a source, use the mask layer as the mask, and just paint the source through the mask. Of course it gets more complicated, because sometimes the source layers use paint, and sometimes fill. Furthermore, if the source layer has an opacity, then we must do a push/pop group because there is no mask with opacity operation in Cairo. In this case, we push the current drawing context, do the paint or fill, then use this new context for the masking source.
Thebes layers are more complex because they use a rotating buffer for drawing to minimise redrawing. Masking is not affected too much though, for each quadrant we just mask as if we were drawing the whole layer, using the mask's transform and ignoring any rotation. The only slight complication is that the mask and its transform must be extracted from the source layer in the basic layers code, and passed to the buffer separately.
The transforms in basic layers work differently to the other backends. In layout, we set up the mask transform the same way, but we use a different method of calculating the effective transform. The actual computation for mask layer transforms is the same, but the matrix passed to ComputeEffectiveTransformForMaskLayer will be different. When we come to rendering, we use only the mask layer's transform for when using the mask, that is, we use SetMatrix, we don't add the mask's transform to the current transform like we do on the GPU backends.
The basic layers backend is always used on the drawing thread when we use OMTC (either the OpenGL or basic backends will be used for compositing). Masking is mostly done on the compositing thread. IPDL does most of the heavy lifting for this, the only thing we have to do is to ensure that if we are only drawing (that is, not also compositing), then we must 'draw' the mask to an off-screen buffer so that it can be used by the compositing thread. Masking is only done if we are compositing also, so when we draw a layer, we check whether to draw it with the mask (if we are compositing) or draw it and its mask separately (if we are only drawing). Of course there is an exception, colour layers are masked on the drawing thread.
When using basic layers, the drawing is done using Cairo, or more precisely, using Thebes our wrapper graphics library. Therefore, we do not (as on the GPU backends) use shaders to do the masking, but resort to actual mask operations. The basic idea is we draw the content un-masked, use that as a source, use the mask layer as the mask, and just paint the source through the mask. Of course it gets more complicated, because sometimes the source layers use paint, and sometimes fill. Furthermore, if the source layer has an opacity, then we must do a push/pop group because there is no mask with opacity operation in Cairo. In this case, we push the current drawing context, do the paint or fill, then use this new context for the masking source.
Thebes layers are more complex because they use a rotating buffer for drawing to minimise redrawing. Masking is not affected too much though, for each quadrant we just mask as if we were drawing the whole layer, using the mask's transform and ignoring any rotation. The only slight complication is that the mask and its transform must be extracted from the source layer in the basic layers code, and passed to the buffer separately.
The transforms in basic layers work differently to the other backends. In layout, we set up the mask transform the same way, but we use a different method of calculating the effective transform. The actual computation for mask layer transforms is the same, but the matrix passed to ComputeEffectiveTransformForMaskLayer will be different. When we come to rendering, we use only the mask layer's transform for when using the mask, that is, we use SetMatrix, we don't add the mask's transform to the current transform like we do on the GPU backends.
The basic layers backend is always used on the drawing thread when we use OMTC (either the OpenGL or basic backends will be used for compositing). Masking is mostly done on the compositing thread. IPDL does most of the heavy lifting for this, the only thing we have to do is to ensure that if we are only drawing (that is, not also compositing), then we must 'draw' the mask to an off-screen buffer so that it can be used by the compositing thread. Masking is only done if we are compositing also, so when we draw a layer, we check whether to draw it with the mask (if we are compositing) or draw it and its mask separately (if we are only drawing). Of course there is an exception, colour layers are masked on the drawing thread.
Sunday, June 24, 2012
Some mask layers optimisations
I've been working on a couple of small optimisations for mask layers, required for Boot to Gecko, but which will help on all platforms.
Drawing the mask layer (bug 757346)
The common case for mask layers is a single rounded rect clip. We would like this to be fast (obviously). The general case is some number of rounded rect clips, in this case the mask is the intersection of these rounded rects. Before mask layers, clipping was done by just drawing each rounded rect, then using that as a clip. Doing this multiple times gives the intersection we want. So, when we did the mask layers work, we kept this method of drawing the mask, we used the rounded rects as clips, and painted alpha = 1 into the whole mask image, giving the desired mask.
Unfortunately, clipping to an arbitrary path like this is often slow (apparently). So, for the common case of one rounded rect, we just draw the rounded rect onto the mask surface (kind of obvious, really). For the general case, we use the first n-1 rounded rects as clips and we draw the last one, again giving the desired effect, and ever so slightly faster, but the real optimisation is for the common case.
Sharing mask images (bug 757347, work in progress)
If we have multiple, similar masks on one page, then currently they get a mask image each. This is not efficient in terms of memory or speed (because the mask has to be created multiple times, which is slow). So we would like multiple mask layers to share a single mask image. This turns out to be more complicated than it sounds.
The basic idea is that we have a global hashtable, and every image we create for a mask is put into it, using the rounded rects used to create it as a key. We keep a count of how many mask layers are using the image, and when that falls to zero, we delete the image. When we need to create a new mask layer, we first check if we can reuse an image from the cache.
This sounds fairly simple, but we need to totally re-organise the way mask layers are built to do this. Fortunately, the changes are limited to the creation of masks and their transforms, the backends did not need to change. Rather than store the part of a mask which overlaps with the masked layer's visible region, we store the whole mask and nothing but the mask. This means that a layer with the same mask in different places can use one image, or different layers can share a single mask if it is at different places within each layer.
The new way to create a mask image is to calculate a bounding rect for the clipping rounded rects, this is in the masked layer's coordinate space. The mask image will be the same size as the bounding rect (modulo a maximum texture size), so the transform for the mask layer simply translates the mask to the right place (formally, it is the transform which takes us from mask space to the masked layer's space, and might involve a scale). For any other layer which reuses the mask, we just need a different transform.
To manage the cache of mask images we create a new class: MaskLayerImageCache, this holds the hashtable which stores the images, and has methods for using the cache. We also need classes for an entry in the hashtable (MaskLayerImageEntry), a key for looking up images (MaskLayerImageKey), and another representation of the rounded rects used to create the mask (PixelRoundedRect). An entry object keeps a reference to the image container (we actually cache the container, not the image itself), and to its key. When we get a hit in the hashtable, we return both the key and the image container, the entry is private to MaskLayerImageCache. The created mask layer (which is an image layer) keeps a reference to the image container. We keep a reference to the key in the mask layer's user data.
(Now it gets interesting), image containers are reference counted and we don't want the container to die when it is still referenced by a mask layer, but nor do we want to keep the image around for ever. So the entry has an owning ref to the image container which keeps it alive (as do the mask layers, but they don't actually need to), we then maintain our own count of how many mask layers reference the image in that image's key, which is primarily maintained by the mask layer's user data (which uses an nsRefPtr). We must separate the key from the entry because the hashtable can move around the entries in memory, and the mask layer (well, its user data) needs a permanent link to something to keep a reference count.
Once the count of mask layers in the key gets to zero we can remove the linked image from the cache, destroying the last reference and causing it to be released. To do this we sweep the cache once the layer tree has been constructed checking for zero reference counts. We do this after building but before the tree is destroyed, so that an image can be unreferenced between layer tree builds and not be destroyed, this means, we can sometimes save building a new mask image if it was used in the previous cycle.
This is all very nice (no, really, it saves us quite a lot of work in some cases), but it is not perfect. The main problem is with OMTC, where the image might be copied across to the parent process multiple times (once for each reference). This is a weakness of our multi-thread system, and needs a separate fix; it ought to be done soon-ish (for other reasons too).
The last problem with this work is that mask images can be shared between backends, and in our earlier work the different backends required different image formats (A8 vs ARGB32). This has been surprisingly difficult to fix, and I'm on about my third attempt, as always, Android is being particularly problematic. Hopefully, I have it sorted now, fingers crossed...
Drawing the mask layer (bug 757346)
The common case for mask layers is a single rounded rect clip. We would like this to be fast (obviously). The general case is some number of rounded rect clips, in this case the mask is the intersection of these rounded rects. Before mask layers, clipping was done by just drawing each rounded rect, then using that as a clip. Doing this multiple times gives the intersection we want. So, when we did the mask layers work, we kept this method of drawing the mask, we used the rounded rects as clips, and painted alpha = 1 into the whole mask image, giving the desired mask.
Unfortunately, clipping to an arbitrary path like this is often slow (apparently). So, for the common case of one rounded rect, we just draw the rounded rect onto the mask surface (kind of obvious, really). For the general case, we use the first n-1 rounded rects as clips and we draw the last one, again giving the desired effect, and ever so slightly faster, but the real optimisation is for the common case.
Sharing mask images (bug 757347, work in progress)
If we have multiple, similar masks on one page, then currently they get a mask image each. This is not efficient in terms of memory or speed (because the mask has to be created multiple times, which is slow). So we would like multiple mask layers to share a single mask image. This turns out to be more complicated than it sounds.
The basic idea is that we have a global hashtable, and every image we create for a mask is put into it, using the rounded rects used to create it as a key. We keep a count of how many mask layers are using the image, and when that falls to zero, we delete the image. When we need to create a new mask layer, we first check if we can reuse an image from the cache.
This sounds fairly simple, but we need to totally re-organise the way mask layers are built to do this. Fortunately, the changes are limited to the creation of masks and their transforms, the backends did not need to change. Rather than store the part of a mask which overlaps with the masked layer's visible region, we store the whole mask and nothing but the mask. This means that a layer with the same mask in different places can use one image, or different layers can share a single mask if it is at different places within each layer.
The new way to create a mask image is to calculate a bounding rect for the clipping rounded rects, this is in the masked layer's coordinate space. The mask image will be the same size as the bounding rect (modulo a maximum texture size), so the transform for the mask layer simply translates the mask to the right place (formally, it is the transform which takes us from mask space to the masked layer's space, and might involve a scale). For any other layer which reuses the mask, we just need a different transform.
To manage the cache of mask images we create a new class: MaskLayerImageCache, this holds the hashtable which stores the images, and has methods for using the cache. We also need classes for an entry in the hashtable (MaskLayerImageEntry), a key for looking up images (MaskLayerImageKey), and another representation of the rounded rects used to create the mask (PixelRoundedRect). An entry object keeps a reference to the image container (we actually cache the container, not the image itself), and to its key. When we get a hit in the hashtable, we return both the key and the image container, the entry is private to MaskLayerImageCache. The created mask layer (which is an image layer) keeps a reference to the image container. We keep a reference to the key in the mask layer's user data.
(Now it gets interesting), image containers are reference counted and we don't want the container to die when it is still referenced by a mask layer, but nor do we want to keep the image around for ever. So the entry has an owning ref to the image container which keeps it alive (as do the mask layers, but they don't actually need to), we then maintain our own count of how many mask layers reference the image in that image's key, which is primarily maintained by the mask layer's user data (which uses an nsRefPtr). We must separate the key from the entry because the hashtable can move around the entries in memory, and the mask layer (well, its user data) needs a permanent link to something to keep a reference count.
Once the count of mask layers in the key gets to zero we can remove the linked image from the cache, destroying the last reference and causing it to be released. To do this we sweep the cache once the layer tree has been constructed checking for zero reference counts. We do this after building but before the tree is destroyed, so that an image can be unreferenced between layer tree builds and not be destroyed, this means, we can sometimes save building a new mask image if it was used in the previous cycle.
This is all very nice (no, really, it saves us quite a lot of work in some cases), but it is not perfect. The main problem is with OMTC, where the image might be copied across to the parent process multiple times (once for each reference). This is a weakness of our multi-thread system, and needs a separate fix; it ought to be done soon-ish (for other reasons too).
The last problem with this work is that mask images can be shared between backends, and in our earlier work the different backends required different image formats (A8 vs ARGB32). This has been surprisingly difficult to fix, and I'm on about my third attempt, as always, Android is being particularly problematic. Hopefully, I have it sorted now, fingers crossed...
Tuesday, June 12, 2012
Mask Layers on the Direct3D backends
In the next few posts I'll describe how mask layers are used in the various graphic backends. The Direct3D 9 and 10 backends are pretty similar, so I'll describe them together. The Direct3D 10 backend is the cleanest, so that's where I will start.
A mask layer is loaded from the surface created in SetupMaskLayer into a DX10 texture in LayerD3D10::LoadMaskTexture. This should be fast because we use a DX10 texture as the backend to that surface. In fact, LoadMaskTexture does more than that, it also sets everything up for the shader to use the mask and returns a flag indicating the kind of shader to use (with a mask or without).
Each DX10 layer class has a GetAsTexture method which returns a texture snapshot of that layer. Currently, that is only implemented for image layers, and it returns the backing texture. This method is called by LoadMaskTexture to get the texture for the mask layer. GetAsTexture returns a shader resource view (SRV) which wraps the texture memory, LoadMaskTexture can simply set this SRV as a resource for the effect (a DX10 abstraction for a group of shaders and state), called tMask (t for texture).
GetAsTexture also returns the size of the texture. LoadMaskTexture uses this and the mask layer's effective transform to calculate the texture's bounding rectangle in the coordinate space which will be used for rendering, this is passed to the effect as vMaskQuad (v for vector, it is just a vector of length four, containing the position and dimensions of the bounding quad).
When a layer is rendered (RenderLayer), a system of shader flags is used (including the flag returned from LoadMaskTexture) to work out which shader to use. LoadMaskTexture us called as part of this calculation, so when we have the shader flags, ready the mask and its quad will be passed to the GPU is they are needed. SelectShader is used to pick the actual shaders (a technique, technically, which is a group of passes, which are combinations of vertex and fragment shaders), and the other arguments are passed to the effect. The technique is called and the layer is rendered.
There is one kind of vertex shader and a bunch of different kinds of fragment shaders (for different colour schemes, etc.). When we added mask layers, we introduced vertex shaders for layers with masks and for layers with masks and a 3D transform. We doubled the number of fragment shaders, adding a version of each for layers with masks (plus a couple of extra for 3D). For masks, the vertex shader calculates the location on the mask at which to sample (in the texture's coordinate space), and the fragment shader pretty much just does a multiply with the alpha value at that sample from the mask and the result of rendering the rest of the layer at that point.
The vertex shader operates on each corner of the rendered quad (which is a rectangular window onto a layer), it figures out the location of the corner it is working in the current coordinate space (which is that of the containing layer) and uses that to calculate a position in the coordinate space of the texture being rendered (an image of the layer). For mask layers, we do likewise to calculate a position on the mask's texture, the graphics hardware interpolates these positions to find texture coords for each pixel.
For layers with a 3D transform (with perspective) this interpolation could lead to distortion because the graphics hardware does perspective correct interpolation, but our mask layer was rendered to the texture, after being transformed, so interpolation should be linear. We therefore have to do a little dance to 'undo' the perspective correct interpolation in any vertex and fragment shaders which could be used on layers with 3D transforms.
DirectX 9 works pretty similarly to the DirectX 10 backend, the shaders and textures work differently, but the concepts are the same. The management of the mask layers changes to reflect the way the LayerManager is written too, but again the changes are minor. On the DirectX 9 backend, we support shadow layers for OMTC, but I'll discuss this stuff when I talk about the OpenGL backend, because that is where more of the effort for OMTC went.
A mask layer is loaded from the surface created in SetupMaskLayer into a DX10 texture in LayerD3D10::LoadMaskTexture. This should be fast because we use a DX10 texture as the backend to that surface. In fact, LoadMaskTexture does more than that, it also sets everything up for the shader to use the mask and returns a flag indicating the kind of shader to use (with a mask or without).
Each DX10 layer class has a GetAsTexture method which returns a texture snapshot of that layer. Currently, that is only implemented for image layers, and it returns the backing texture. This method is called by LoadMaskTexture to get the texture for the mask layer. GetAsTexture returns a shader resource view (SRV) which wraps the texture memory, LoadMaskTexture can simply set this SRV as a resource for the effect (a DX10 abstraction for a group of shaders and state), called tMask (t for texture).
GetAsTexture also returns the size of the texture. LoadMaskTexture uses this and the mask layer's effective transform to calculate the texture's bounding rectangle in the coordinate space which will be used for rendering, this is passed to the effect as vMaskQuad (v for vector, it is just a vector of length four, containing the position and dimensions of the bounding quad).
When a layer is rendered (RenderLayer), a system of shader flags is used (including the flag returned from LoadMaskTexture) to work out which shader to use. LoadMaskTexture us called as part of this calculation, so when we have the shader flags, ready the mask and its quad will be passed to the GPU is they are needed. SelectShader is used to pick the actual shaders (a technique, technically, which is a group of passes, which are combinations of vertex and fragment shaders), and the other arguments are passed to the effect. The technique is called and the layer is rendered.
There is one kind of vertex shader and a bunch of different kinds of fragment shaders (for different colour schemes, etc.). When we added mask layers, we introduced vertex shaders for layers with masks and for layers with masks and a 3D transform. We doubled the number of fragment shaders, adding a version of each for layers with masks (plus a couple of extra for 3D). For masks, the vertex shader calculates the location on the mask at which to sample (in the texture's coordinate space), and the fragment shader pretty much just does a multiply with the alpha value at that sample from the mask and the result of rendering the rest of the layer at that point.
The vertex shader operates on each corner of the rendered quad (which is a rectangular window onto a layer), it figures out the location of the corner it is working in the current coordinate space (which is that of the containing layer) and uses that to calculate a position in the coordinate space of the texture being rendered (an image of the layer). For mask layers, we do likewise to calculate a position on the mask's texture, the graphics hardware interpolates these positions to find texture coords for each pixel.
For layers with a 3D transform (with perspective) this interpolation could lead to distortion because the graphics hardware does perspective correct interpolation, but our mask layer was rendered to the texture, after being transformed, so interpolation should be linear. We therefore have to do a little dance to 'undo' the perspective correct interpolation in any vertex and fragment shaders which could be used on layers with 3D transforms.
DirectX 9 works pretty similarly to the DirectX 10 backend, the shaders and textures work differently, but the concepts are the same. The management of the mask layers changes to reflect the way the LayerManager is written too, but again the changes are minor. On the DirectX 9 backend, we support shadow layers for OMTC, but I'll discuss this stuff when I talk about the OpenGL backend, because that is where more of the effort for OMTC went.
Thursday, June 07, 2012
More on my new phone
So I am still pretty much in geek-love with my phone (HTC One X). But there has been something about it that has been annoying me and I have only just worked out what it is. I'm not sure quite how to phrase this, but using the phone for passive computing tasks is amazing, better (mostly) than using a proper computer. Reading stuff on the internet, listening to music, watching videos, playing games, and so forth, all an awesome experience. But, anything that involves active interaction is frustrating to the point of impossible - writing an email, doing some coding, in fact, getting any work done at all. This is kind of obvious given the input methods.
To put it another way, the device is perfect for consumption, but terrible for creation. This bother me because, for me, using a computer has always been a creative experience; the whole point is to make things. For me, the phone is much more like a TV then a computer in terms of interaction, and that makes me sad.
It is an amazingly powerful device, and seems to me that I ought to be productive with it, but the only useful thing I've done with it is testing Firefox. I suppose in a way, it's good, it means I don't need to get too attached to another expensive gadget.
To put it another way, the device is perfect for consumption, but terrible for creation. This bother me because, for me, using a computer has always been a creative experience; the whole point is to make things. For me, the phone is much more like a TV then a computer in terms of interaction, and that makes me sad.
It is an amazingly powerful device, and seems to me that I ought to be productive with it, but the only useful thing I've done with it is testing Firefox. I suppose in a way, it's good, it means I don't need to get too attached to another expensive gadget.
Tuesday, June 05, 2012
An ill-thought out theory about what makes programming interesting
This one is going to be a bit random. Bear with me. I've been thinking a bit about what makes some programming tasks interesting and some not so interesting (to me). As a result of this thinking, I present my theory of different kinds of programming (TM). I'm sure someone has come up with this before, but I've not come across it, I think.
So, let us define normal programs as 1st order programming, they operate on data and produce an output. Most programming tasks are of this nature. Let us call data itself 0th order programming, that is, there is no real programming. 2nd order programs are those that operate on 1st order programs (for e.g., compilers, modern web browsers); 3rd order programs operate on 2nd order ones (e.g., compiler-compilers, parser generators, tools for the analysis of compilers or compiler theories, such as Coq); and so forth, although I can't think of any 4th order programs, and as with most nth-order type theories, the higher orders blur together and probably stop being interesting.
Furthermore, we can have half orders, where the programming task is meant to be extensively reused. So standard libraries and frameworks are 1.5th order and compiler libraries and so forth (e.g., llvm) are 2.5th order. Possibly there are 0.5th order programs, but I don't think of libraries here so much as hybrid data/programs such as a TeX document.
I think that from a programming perspective, the problems get more interesting as we go up the scale (for some definition of interesting, which might just be complicated). So, for a programmer, making a web page (0th order) is boring as hell, making web-based software is much more interesting, and making a compiler for that software is more interesting still. In fact, I don't think it is just about complicated, I think that as we go up the scale the problems are qualitatively different (and, to me at least, more interesting).
BUT, there are advantages to lower-order programming, and disadvantages to higher-order programming: working with data, you can be creative and solve hard problems about all kinds of non-progamming things. Likewise, 1st order programs tend to allow you to work closer to the 'people' problems, which, apparently, are the really interesting ones. The lower order a program is (in general), the easy it is to test and to specify the problem (the lack of a clear specification being one of the most annoying things, for me, about programming). As we go up the orders, the tasks can actually get repetitive, and certainly the risk of failure is higher, the problem more abstract and has a less direct impact on the real world. And at some point the complexity stops being fun - I have dabbled in a few 3rd order tasks, and progress was very slow, and the output very small, and a lot of the problems encountered were tedious edge cases.
So thinking about myself, 2nd order programming seems to be my Goldilocks kind of programming, not too abstract and complex, but operating on code, not data. All the projects I have really enjoyed fall into this category - compilers, interpreters, Firefox.
I wonder where programming language theory falls into my scheme. I think of it as just programming really, but with maths, rather than a compiler. It doesn't feel like any of my categories though (but has elements of all of them), maybe I need a different scheme.
So, let us define normal programs as 1st order programming, they operate on data and produce an output. Most programming tasks are of this nature. Let us call data itself 0th order programming, that is, there is no real programming. 2nd order programs are those that operate on 1st order programs (for e.g., compilers, modern web browsers); 3rd order programs operate on 2nd order ones (e.g., compiler-compilers, parser generators, tools for the analysis of compilers or compiler theories, such as Coq); and so forth, although I can't think of any 4th order programs, and as with most nth-order type theories, the higher orders blur together and probably stop being interesting.
Furthermore, we can have half orders, where the programming task is meant to be extensively reused. So standard libraries and frameworks are 1.5th order and compiler libraries and so forth (e.g., llvm) are 2.5th order. Possibly there are 0.5th order programs, but I don't think of libraries here so much as hybrid data/programs such as a TeX document.
I think that from a programming perspective, the problems get more interesting as we go up the scale (for some definition of interesting, which might just be complicated). So, for a programmer, making a web page (0th order) is boring as hell, making web-based software is much more interesting, and making a compiler for that software is more interesting still. In fact, I don't think it is just about complicated, I think that as we go up the scale the problems are qualitatively different (and, to me at least, more interesting).
BUT, there are advantages to lower-order programming, and disadvantages to higher-order programming: working with data, you can be creative and solve hard problems about all kinds of non-progamming things. Likewise, 1st order programs tend to allow you to work closer to the 'people' problems, which, apparently, are the really interesting ones. The lower order a program is (in general), the easy it is to test and to specify the problem (the lack of a clear specification being one of the most annoying things, for me, about programming). As we go up the orders, the tasks can actually get repetitive, and certainly the risk of failure is higher, the problem more abstract and has a less direct impact on the real world. And at some point the complexity stops being fun - I have dabbled in a few 3rd order tasks, and progress was very slow, and the output very small, and a lot of the problems encountered were tedious edge cases.
So thinking about myself, 2nd order programming seems to be my Goldilocks kind of programming, not too abstract and complex, but operating on code, not data. All the projects I have really enjoyed fall into this category - compilers, interpreters, Firefox.
I wonder where programming language theory falls into my scheme. I think of it as just programming really, but with maths, rather than a compiler. It doesn't feel like any of my categories though (but has elements of all of them), maybe I need a different scheme.
Tuesday, May 29, 2012
Building a mask layer
Mask layers are built in layout/base/FrameLayerBuilder.cpp. Most of the work constructing the mask layer is done in SetupMaskLayer (which I guess should actually be called SetupMaskLayerForRoundedRectClip or something). But before that, we have to figure out if making a mask layer makes sense or not.
This is easy for image, colour, and container layers. But for Thebes layers it is more complicated, there can be multiple display items in a single Thebes layer, and we can only create a mask for the rounded rect clips that all items have in common. In practice, this is usually one clip, and often when there is only one item in the layer, but we cope with more. As items are added to a Thebes layer we keep track of the number of rounded rect clips in common using ThebesLayerData::mCommonClipCount, mostly in ThebesLayerData::UpdateCommonClipCount. We keep the clip for some item in the layer in UpdateCommonClipCount::mItemClip, the first mCommonClipCount clips in this clip are common to all items in the layer (we only find common clips if they are the first for each item). As we add items to the layer, their clips are compared to mItemClip, and mCommonClipCount is updated as necessary.
When Thebes layers are popped from the stack (i.e., we are done building), then mCommonClipCount is moved to ThebesLayerEntry::mCommonClipCount (it must be initialised, i.e., greater than zero by now). We create a mask layer for the first mCommonClipCount clipping rects. When the thebes layer is drawn, we only clip for clipping rounded rects other than the common ones.
FrameLayerBuilder has a neat way of recycling layers, this is a combination of caching and memory management: we recycle and create layers in order and if we get back the same layer as we had last time round (common case) we don't bother to rebuild it, but leave the layer as is. We do a similar thing with mask layers. This is a bit complicated because we only guarantee that layers of the same type are recycled in order, so we need to keep lists of mask layers for each type of layer. We store information about the clips we are masking for in the user data on the mask layer, this is checked in SetupMaskLayer to see if we have to build the mask fresh, or if we can get away with re-using the old version. Thus, we avoid building the mask too often.
When the mask is built in FrameLayerBuilder.cpp, we create a mask surface which is the same size as the masked layer's visible region. We paint the clip into this surface, but only the relevant bits of the clip will be inside the surface. So, the mask is in it's own coordinate system, which is relative to the masked layer's visible region. We create a transform for the mask which transforms the mask's coordinate system to the masked layer's coordinate system. (Note, I'm currently changing this stuff, so it might not be true for long). After the layer tree is built, it is walked to compute the effective transform of each layer (this means different things for the different backends). We updated this walk to also calculate an effective transform for mask layers. So, when we come to render the layer tree, the effective transform for the mask layer is the one that we need for drawing the mask layer 'on top of' the masked layer's visible region, however the masked layer is rendered (I'll describe the transform in more detail in later posts).
This is easy for image, colour, and container layers. But for Thebes layers it is more complicated, there can be multiple display items in a single Thebes layer, and we can only create a mask for the rounded rect clips that all items have in common. In practice, this is usually one clip, and often when there is only one item in the layer, but we cope with more. As items are added to a Thebes layer we keep track of the number of rounded rect clips in common using ThebesLayerData::mCommonClipCount, mostly in ThebesLayerData::UpdateCommonClipCount. We keep the clip for some item in the layer in UpdateCommonClipCount::mItemClip, the first mCommonClipCount clips in this clip are common to all items in the layer (we only find common clips if they are the first for each item). As we add items to the layer, their clips are compared to mItemClip, and mCommonClipCount is updated as necessary.
When Thebes layers are popped from the stack (i.e., we are done building), then mCommonClipCount is moved to ThebesLayerEntry::mCommonClipCount (it must be initialised, i.e., greater than zero by now). We create a mask layer for the first mCommonClipCount clipping rects. When the thebes layer is drawn, we only clip for clipping rounded rects other than the common ones.
FrameLayerBuilder has a neat way of recycling layers, this is a combination of caching and memory management: we recycle and create layers in order and if we get back the same layer as we had last time round (common case) we don't bother to rebuild it, but leave the layer as is. We do a similar thing with mask layers. This is a bit complicated because we only guarantee that layers of the same type are recycled in order, so we need to keep lists of mask layers for each type of layer. We store information about the clips we are masking for in the user data on the mask layer, this is checked in SetupMaskLayer to see if we have to build the mask fresh, or if we can get away with re-using the old version. Thus, we avoid building the mask too often.
When the mask is built in FrameLayerBuilder.cpp, we create a mask surface which is the same size as the masked layer's visible region. We paint the clip into this surface, but only the relevant bits of the clip will be inside the surface. So, the mask is in it's own coordinate system, which is relative to the masked layer's visible region. We create a transform for the mask which transforms the mask's coordinate system to the masked layer's coordinate system. (Note, I'm currently changing this stuff, so it might not be true for long). After the layer tree is built, it is walked to compute the effective transform of each layer (this means different things for the different backends). We updated this walk to also calculate an effective transform for mask layers. So, when we come to render the layer tree, the effective transform for the mask layer is the one that we need for drawing the mask layer 'on top of' the masked layer's visible region, however the masked layer is rendered (I'll describe the transform in more detail in later posts).
Sunday, May 27, 2012
Assembly - strings
I want to find out a little about how strings work in assembly, and as a side effect call some functions that I haven't defined. So I will try to encode the following rather contrived example:
char* hello = "hello";
char* world = "world";
char* helloWorld = (char*)malloc(64);
strcpy(helloWorld, hello);
helloWorld[5] = ' ';
strcpy(helloWorld+6, world);
printf("%s!\n", helloWorld);
The interesting bits are stack (I'm going to allocate the format string on the stack) and heap allocation (the latter done by malloc), copying strings and doing some character manipulation and calling a function which takes a variable number of arguments. I will make the hello and world strings global variables. Here is the assembly:
// allocate on the heap for helloWorld
push 64
call malloc
add esp, 4
// save address of helloWorld on the stack
push eax
// copy hello to helloWorld
mov ebx, 0
mov ecx, hello
copyh:
mov dl, BYTE PTR [ebx+ecx]
mov BYTE PTR [eax], dl
inc eax
inc ebx
cmp ebx, 5
jl copyh
// add a space
mov [eax], ' '
inc eax
// copy world to helloWorld
mov ebx, 0
mov ecx, world
copyw:
mov dl, BYTE PTR [ecx+ebx]
mov BYTE PTR [eax], dl
inc eax
inc ebx
cmp ebx, 5
jl copyw
// null terminate helloWorld
mov [eax], 0
// temporarily move address of helloWorld to eax
pop eax
// allocate format on the stack and save address in ebx
sub esp, 8
mov ebx, esp
// create format
mov byte ptr [ebx], '%'
mov byte ptr [ebx+1], 's'
mov byte ptr [ebx+2], '!'
mov byte ptr [ebx+3], '\n'
mov byte ptr [ebx+4], 0
// call printf
push eax
push ebx
call printf
// tidy up printf call and format
add esp, 16
// should really call delete, but meh
One thing that surprised me is that you don't need to pass the number of vararg arguments - the callee just has to work it out! Getting the call to malloc working was a pain, I had to link the standard library statically rather than as a dll, and a whole bunch of other compilation options which I don't know whether they affected it or not (compile as C, not C++, turn off randomised addressing, etc.).
char* hello = "hello";
char* world = "world";
char* helloWorld = (char*)malloc(64);
strcpy(helloWorld, hello);
helloWorld[5] = ' ';
strcpy(helloWorld+6, world);
printf("%s!\n", helloWorld);
The interesting bits are stack (I'm going to allocate the format string on the stack) and heap allocation (the latter done by malloc), copying strings and doing some character manipulation and calling a function which takes a variable number of arguments. I will make the hello and world strings global variables. Here is the assembly:
// allocate on the heap for helloWorld
push 64
call malloc
add esp, 4
// save address of helloWorld on the stack
push eax
// copy hello to helloWorld
mov ebx, 0
mov ecx, hello
copyh:
mov dl, BYTE PTR [ebx+ecx]
mov BYTE PTR [eax], dl
inc eax
inc ebx
cmp ebx, 5
jl copyh
// add a space
mov [eax], ' '
inc eax
// copy world to helloWorld
mov ebx, 0
mov ecx, world
copyw:
mov dl, BYTE PTR [ecx+ebx]
mov BYTE PTR [eax], dl
inc eax
inc ebx
cmp ebx, 5
jl copyw
// null terminate helloWorld
mov [eax], 0
// temporarily move address of helloWorld to eax
pop eax
// allocate format on the stack and save address in ebx
sub esp, 8
mov ebx, esp
// create format
mov byte ptr [ebx], '%'
mov byte ptr [ebx+1], 's'
mov byte ptr [ebx+2], '!'
mov byte ptr [ebx+3], '\n'
mov byte ptr [ebx+4], 0
// call printf
push eax
push ebx
call printf
// tidy up printf call and format
add esp, 16
// should really call delete, but meh
One thing that surprised me is that you don't need to pass the number of vararg arguments - the callee just has to work it out! Getting the call to malloc working was a pain, I had to link the standard library statically rather than as a dll, and a whole bunch of other compilation options which I don't know whether they affected it or not (compile as C, not C++, turn off randomised addressing, etc.).
Saturday, May 26, 2012
Mask Layers
The bulk of my work at Mozilla so far has been on mask layers. These
just landed (bug 716439) and should be in Aurora at the next uplift. I'm
going to try and explain the work in some detail over a series of blog
posts. Here I'll try to give an overview.
The motivation for mask layers is to allow fast (hardware accelerated) clipping. Before mask layers, clipping to a rectangle is basically free, but clipping to any other shape is extremely expensive, because it was not done on graphics hardware. A particularly example is rectangles with rounded corners, so a video clipped to a rectangle was very smooth, but as soon as you use CSS border-radius, it would degrade horribly.
Mask layers solve this by adding a mask layer to each layer in the layer tree (which is just null if no masking is needed), the alpha of the mask is used when compositing layers, which clips anything where the mask alpha is zero.
At present there is only support for image layers as mask layers, so the mask is simply a bitmap in memory, but there is no reason other layer types cannot be supported. Mask layers are currently only used to support rounded corner rectangles, but the mechanism is fully general.
So, overview: when building an active layer (no masks on inactive layers) in FrameLayerBuilder, if an image, colour, or container layer has a rounded rect clip, or a all items in a Thebes layer have the same rounded rect clip, then we create a mask layer for that layer. When rendering the layers, the mask is used whilst compositing. This means that in OMTC, masking is done on the compositor thread, and the mask layer is passed across as part of the PLayers protocol.
In the hardware backends, the masking is done using shaders. For each shader that used to exist, we create an extra one which does the masking as well. In fact, for some shaders we need a third shader for masks with a 3D transform, because we must take account of perspective-correct (which is incorrect, in our case) interpolation done by the GPU.
On the basic layers backend, masking is done using Cairo masking.
Inactive layers are done the old way, that is, when the layer is drawn, and rounded rect clips on content are clipped using Thebes. There is new work (Bug 755078) to enable turning mask layers on or off at compile time using the MOZ_ENABLE_MASK_LAYERS flag. It might be necesssary to do this on mobile because the mask layers are not playing nice with tiled textures (although hopefully, this is fixed now).
The motivation for mask layers is to allow fast (hardware accelerated) clipping. Before mask layers, clipping to a rectangle is basically free, but clipping to any other shape is extremely expensive, because it was not done on graphics hardware. A particularly example is rectangles with rounded corners, so a video clipped to a rectangle was very smooth, but as soon as you use CSS border-radius, it would degrade horribly.
Mask layers solve this by adding a mask layer to each layer in the layer tree (which is just null if no masking is needed), the alpha of the mask is used when compositing layers, which clips anything where the mask alpha is zero.
At present there is only support for image layers as mask layers, so the mask is simply a bitmap in memory, but there is no reason other layer types cannot be supported. Mask layers are currently only used to support rounded corner rectangles, but the mechanism is fully general.
So, overview: when building an active layer (no masks on inactive layers) in FrameLayerBuilder, if an image, colour, or container layer has a rounded rect clip, or a all items in a Thebes layer have the same rounded rect clip, then we create a mask layer for that layer. When rendering the layers, the mask is used whilst compositing. This means that in OMTC, masking is done on the compositor thread, and the mask layer is passed across as part of the PLayers protocol.
In the hardware backends, the masking is done using shaders. For each shader that used to exist, we create an extra one which does the masking as well. In fact, for some shaders we need a third shader for masks with a 3D transform, because we must take account of perspective-correct (which is incorrect, in our case) interpolation done by the GPU.
On the basic layers backend, masking is done using Cairo masking.
Inactive layers are done the old way, that is, when the layer is drawn, and rounded rect clips on content are clipped using Thebes. There is new work (Bug 755078) to enable turning mask layers on or off at compile time using the MOZ_ENABLE_MASK_LAYERS flag. It might be necesssary to do this on mobile because the mask layers are not playing nice with tiled textures (although hopefully, this is fixed now).
Assembly - calling conventions - callees
The callee has to do the other side of the handshake I discussed last time. But it also has to do a little more housekeeping. There are two registers which point into the stack, esp points to the top of the stack and is kept up to date by push/pop. ebp is the base pointer and points to the bottom of the current stack frame. It must be set when we create a new stack frame, such as when we enter a function. Since ebp is a callee-preserved register we must save the old value of ebp to the stack and later restore it.
cdecl
void __declspec(naked) copy(...)
{
__asm {
//prologue
push ebp
mov ebp, esp
push esi
//copy
mov eax, [ebp+12]
mov esi, [ebp+8]
cmp eax, esi
je finish
mov ecx, [ebp+16]
start:
mov dl, BYTE PTR [esi+ecx]
mov BYTE PTR [eax+ecx], dl
loop start
mov dl, BYTE PTR [esi]
mov BYTE PTR [eax], dl
finish:
//epilogue
pop esi
pop ebp
ret
}
}
I've elided the arguments to the function (since we are doing the calling now, they are irrelevant). The __declspec(naked) declaration means that the compiler will not generate prologue and epilogue for the function. Our epilogue saves ebp to the stack, moves esp to ebp and saves esi to the stack. In the epilogue, esi is restored (it is the only register we need to preserve), then restore ebp. Because there are no push/pops in the body of the function, the stack pointer is correct. The body of the function is pretty much unchanged, the only difference is that we access the arguments by offset from ebp (i.e., in the stack), rather than by name.
Normally, we would store the arguments on the stack, somewhere between ebp and esp, but here we never take them out of the registers, so no need. We would often allocate memory on the stack (also between ebp and esp) for local variables, but we don't need to do that either.
fastcall
Here, we get the arguments in registers, we could copy them to the stack, but we don't need to, so we'll just use them. Because we don't pass anything on the stack, there is nothing to tidy up. We could avoid a couple of moves by using different registers, but I haven't.
//prologue
push ebp
mov ebp, esp
push edi
//fillWithCount
mov edi, ecx
mov ecx, edx
dec ecx
start:
mov BYTE PTR [edi+ecx], cl
loop start
mov BYTE PTR [edi], cl
//epilogue
pop edi
pop ebp
ret
stdcall
Here the arguments are on the stack, and we must restore it on exit.
//prologue
push ebp
mov ebp, esp
push edi
push ebx
//fill
mov edi, [ebp+8]
mov ebx, [ebp+12]
mov ecx, [ebp+16]
dec ecx
start:
mov BYTE PTR [edi+ecx], bl
loop start
mov BYTE PTR [edi], bl
//epilogue
pop ebx
pop edi
pop ebp
ret 12
We use the arguments in the same way as for the cdecl function. The difference is that the ret instruction takes an argument, the number of bytes to pop from the stack in order to tidy up. We could also do this manually:
pop edx
add esp, 12
jmp edx
cdecl
void __declspec(naked) copy(...)
{
__asm {
//prologue
push ebp
mov ebp, esp
push esi
//copy
mov eax, [ebp+12]
mov esi, [ebp+8]
cmp eax, esi
je finish
mov ecx, [ebp+16]
start:
mov dl, BYTE PTR [esi+ecx]
mov BYTE PTR [eax+ecx], dl
loop start
mov dl, BYTE PTR [esi]
mov BYTE PTR [eax], dl
finish:
//epilogue
pop esi
pop ebp
ret
}
}
I've elided the arguments to the function (since we are doing the calling now, they are irrelevant). The __declspec(naked) declaration means that the compiler will not generate prologue and epilogue for the function. Our epilogue saves ebp to the stack, moves esp to ebp and saves esi to the stack. In the epilogue, esi is restored (it is the only register we need to preserve), then restore ebp. Because there are no push/pops in the body of the function, the stack pointer is correct. The body of the function is pretty much unchanged, the only difference is that we access the arguments by offset from ebp (i.e., in the stack), rather than by name.
Normally, we would store the arguments on the stack, somewhere between ebp and esp, but here we never take them out of the registers, so no need. We would often allocate memory on the stack (also between ebp and esp) for local variables, but we don't need to do that either.
fastcall
Here, we get the arguments in registers, we could copy them to the stack, but we don't need to, so we'll just use them. Because we don't pass anything on the stack, there is nothing to tidy up. We could avoid a couple of moves by using different registers, but I haven't.
//prologue
push ebp
mov ebp, esp
push edi
//fillWithCount
mov edi, ecx
mov ecx, edx
dec ecx
start:
mov BYTE PTR [edi+ecx], cl
loop start
mov BYTE PTR [edi], cl
//epilogue
pop edi
pop ebp
ret
stdcall
Here the arguments are on the stack, and we must restore it on exit.
//prologue
push ebp
mov ebp, esp
push edi
push ebx
//fill
mov edi, [ebp+8]
mov ebx, [ebp+12]
mov ecx, [ebp+16]
dec ecx
start:
mov BYTE PTR [edi+ecx], bl
loop start
mov BYTE PTR [edi], bl
//epilogue
pop ebx
pop edi
pop ebp
ret 12
We use the arguments in the same way as for the cdecl function. The difference is that the ret instruction takes an argument, the number of bytes to pop from the stack in order to tidy up. We could also do this manually:
pop edx
add esp, 12
jmp edx
Subscribe to:
Posts (Atom)