In my previous post, I mentioned that I had rewritten the selection renderer in Paint.NET v3.5. As a pseudo-warning, this post is pretty technical.

The selection renderer in Paint.NET v3.36 uses GDI+. It draws the outline twice: once as a dashed black line, and the second as a dashed white line. A timer fires every 50 milliseconds or so and redraws the outline with a slightly increased “dash offset.” This gives the “dancing ants” animation. Our pal Emma Roberts will demonstrate:

 
“Pretend I’m animated!” — Ants

There are a few major problems with this implementation. The first is that while you are drawing or modifying a selection, it is only drawn with a black outline (once you are done, it will transition to the “dancing ants” mode). This makes it wickedly difficult to figure out what kind of selection you’re drawing if the underlying area is black. Try it with a solid black image and you’ll understand immediately. I had to do a solid outline instead of a dashed one because there were some horrible artifacts and performance problems if I didn’t.

Next up, the new render cache (hopefully I’ll discuss it in an upcoming post) splits up rendering into more tiles than it did before (for several good reasons!). GDI+ does not do multithreading. At all. In fact, it actively prevents you from making GDI+ calls on more than one thread even if you are clever and “trick” it. This was resulting in selection rendering performance falling off a cliff as all sorts of “setup” work (creating brushes, clipping, etc.) was being over-executed by up to a factor of 10 (that’s an estimate). Not to mention it was a non-starter for multithreaded performance scaling anyway.

Another problem is that the “dancing ants” animation consumes a lot of CPU power. This in turn slows down the rest of the system, and drains battery power (I’m a desktop/workstation guy, but the market has been majority-owned by laptops for awhile now). There are a few optimizations in there to throttle CPU usage if it gets “too high” but it’s never really been profiled or quantitatively proven to work well. My criteria at the time was “fewer people are complaining,” and then I went and drank beer (woohoo!).

Ahem. Anyway. The animation is really there for two reasons: not only does it look cool, but it guarantees contrast between the selection outline and the underlying image. The image you’re working on can’t animate, but the selection outline does, so there you go: it will never be confused for being part of the image.

The solution? I wrote my own polygon rasterizer renderer. From scratch. There’s a good reason people use libraries like GDI+ and Cairo to render graphics for them: it’s tricky! Get someone else to do it for you! Simple implementations aren’t difficult, but the complexity skyrockets once you add things like antialiasing, clipping, blending, various types of caching, serialization (critical for undo/redo), and safe multithreading.

However, I felt it was worth it to implement just enough of a pixel-pushing geometry rasterization “library” in order to render the selection since it is so crucial for Paint.NET. It’s taken “only” 2 months to get right, and it still isn’t quite finished. (but hey, if something is a core business of yours, do it yourself!). I’m now taking polygon lists and doing my own clipping, scanline rasterization, clipping, blending, etc. It’s fun, confusing, educational, and horrifying. I should probably have a cigarette once I’m all done and calmed down.

Bresenham invented the classic aliased line rasterization algorithm, and a kid named Xiaolin Wu later invented a smart antialiased rasterization algorithm. Both are in wide use today because of their inherent and wonderful simplicity. I implemented the latter, because antialiasing is important. The selection outline now uses “XOR” blending, so contrast is guaranteed except for a few less-common scenarios (prevalent 50% grey).

Notice how in this new screenshot, the selection outline effectively changes color as it goes through parts of the image which are varying colors. Where her hair is dark, the selection is bright, and where it crosses her lighter skin tone it becomes darker:

Normally you can’t use both XOR and antialiasing. XOR is meant to be “undoable” and so applying it a 2nd time simply gives you back the original data. It’s generally fast, cheap, and simple. With a naive antialiasing implementation you end up with seams and dots all over your polygon, as endpoints of lines give you pixels that are rendered twice, and very small lines (0 to 2 pixels long) don’t really know what to do.

My solution was to do the rendering in two passes. In the first pass I accumulate coverage values into the alpha channel. I accumulate towards zero, and use the inverse of that later as my real alpha value. I can do this because I know that the pixel is fully opaque at this stage in the rendering pipeline; this is because the “checkerboard” has already been applied. Thus, the alpha channel can be used for whatever I want.

In the second pass I apply the XOR operator to every pixel along the path at full strength (yar!), and then use alpha blending between the original pixel’s color value and the XOR’d color value with respect to the accumulated alpha. Yes, I’m doing stencil buffer accumulation in software. Video games use these a lot, especially for things like shadows and dancing teddy bears (ok maybe not the second one so much).

Oh, also, the selection is no longer animated because contrast is achievable without it, and because the performance benefit is profound. It would also be much more difficult to get an animated or dotted outline with the new code. I’d need 4x the lines of code, or I’d have to employ code generators or some other form of voodoo (if this were C++, a “policy-based template something-or-other” would be employed). As it is I still have a few higher-order functions and closures in there I need to get rid of. But the performance is still great, so I have deferred those optimizations until later (alpha or beta).

Because the selection renderer is now implemented in code that is completely owned by me, all opportunities for optimization are available. This includes changing the underlying storage model that defines the selection’s polygons – I now use a List of Point arrays (List<System.Windows.Point[]>), which makes interoperating with GPC and WPF easier and faster. I can optimize my clipping and do work ahead of time to ensure that rendering is fast.

I can split work like vector/matrix multiplication across multiple threads. I can even prefetch work ahead of time using “spare” CPU cycles. For instance, whenever the selection changes (moves, rotates, or is edited using add/subtract/union/intersection), I have to recompute the scans of the selection. This is a list of rectangles that I use to fill the interior of the selection with a blue tint. Well, in between the notification of a changed selection, and actually painting it (other stuff happens in the middle), I compute these scans in a background thread. This is a future at work for you!

Also, I can make sure that these “scans” are computed and stored in sorted order with respect to their top Y coordinate. Then, when clipping the rendering of the highlighted selection interior, I can use a nicely fast binary search to figure out which “scan” to start rendering from. Later on I’ll put in logic so that the computation itself can be clipped (I never render the highlight outside of the image bounds, so why calculate that part?). Oh, and did I mention that along the way I found some code on the critical path for the Magic Wand that was using insertion sort? I didn’t? Well, it’s fixed. That was embarrassing.

Other opportunities for optimization include being smarter about which areas of the canvas are redrawn when things change. With GDI+, it was difficult to do the boolean path algebra correctly (because of bugs in GDI+) to find a minimal invalidation region, and so several heuristics were put into place. Now that I control all of the code for both rendering and computational geometry, I’ve been able to implement this better. This improves performance, and fixes some visual glitches whereby little bits and pieces of the selection outline remained when moving/rotating a selection (the heuristic to fix this was, “every 1 second, redraw everything”).

This has all also served to help reacquaint myself with the Paint.NET codebase in areas that haven’t really seen much change in at least 2 years. Therefore, I’m better prepared for more refactoring after v3.5’s release. I’m changing gears for my work on v3.5: I’m going to stop fixing/refactoring things, and move to bugfixing mode. I’ve done a lot of optimizations, and there are still many more possible ones, but I also need to release something so that you all can use it! More optimizations can be trickled out over v3.5.1 or v3.6 releases, etc.

Anyway, that’s all for now. I hope you all will like it. One of my private beta testers sure does:

“…the speed improvements in comparison to my memory of v3.36 are greatly improved on any Windows machine I throw it at. Really well done! I think that this alone will be enough to make people excited.”

I sat down to write some notes before starting this blog entry, and I wound up with two full pages in OneNote on the 1920×1200 monitor it was sitting in. The more I’ve been working on it the more I’m excited about the Paint.NET v3.5 release. It isn’t one that introduces a lot of really cool or big-ticket features, but the list of small improvements is really adding up. I’ve been able to do a lot of research and prototyping in esoteric areas of multithreading and concurrency, and have gained both more mastery and more fear for these topics.

Performance work in Paint.NET v3.5 has wound up focusing on 3 areas:

1. Scaling up. As everyone’s been saying for years, the future is increasingly multithreaded. My newest CPU upgrade leaves me with 8 threads in Task Manager (Intel Core i7 overclocked to 3.8GHz). A lot of research and work has gone into making sure that Paint.NET continues to scale with more threads, and that I have better tools for safely and correctly implementing this across more of the application.

   ”A high-end 64-bit Intel Core i7 desktop should run Paint.NET very fast.”

    

2. Scaling down. Those $300 netbooks that are taking everyone by storm only run about as fast as what I was using 7 years ago (Pentium 4 at 2.0 – 2.5ghz). Clearly, classic optimization strategies are important as well: trimming cycles, removing or deferring code execution, and optimizing repainting.

   “A brand-new netbook with an Atom processor should run Paint.NET comfortably.”

   

3. Reducing memory usage. I guess this goes with scaling down. I made a bet a long time ago that 64-bit would slowly take care of the way I was allocating memory, which simplified development work but has had the consequence of consuming vast amounts of virtual address space . I was wrong: 32-bit will be here for a long time, especially since most of those hot-like-pancakes $300 netbooks are not 64-bit capable. This is currently my top reliability issue, as running out of memory causes Paint.NET to crash.

   ”It’s not all yours.”

   

I’ve had to split this discussion over several blog entries because otherwise it was too long and even I would have fallen asleep reading it. I’ll summarize the results here though:

• Images open much faster, especially on single-core/single-thread systems. Actually, I already wrote about this, so go read that first 🙂
• I ordered and assembled my own Atom-based mini-desktop (“nettop”), in order to keep myself honest as I was working on my Core 2 Quad QX6700 2.67 GHz monster and subsequently as I upgraded to a Core i7 920 2.66GHz overclocked to 3.8 GHz.
• The selection renderer has been completely rewritten. No more dancing ants and no more GDI+ means much lower CPU usage and better performance with multiple CPU cores.
• Much better CPU scaling for the image composition rendering pipeline using LINQ-esque functional programming and deferred execution techniques.
• A rewritten “render cache” has resulted in an average of 30-50% less memory usage when opening multiple images, especially those with just a single layer (PNG, JPEG). This means fewer out of memory crashes, and the ability to open more images without out-of-memory errors.

Paint.NET v3.5 is a stepping stone towards a hopefully epic v4.0. I’m slowly rebuilding the application from the inside out, and it takes a lot of time to do the necessary research and development. About 2 years ago, right around the time I was preparing to release Paint.NET v3.0, I had this nagging feeling in the back of my head that said basically “ur doin’ it wrong”. My document model was wrong, my application model was brittle, and I just couldn’t implement really cool features without using up a ton of memory. I also couldn’t provide features like scripting or a better extensibility model (plugins) in a manner that was both safe and powerful.

However, I didn’t really know how to solve all of this at a scale lower than the 50,000-foot view. Since then I’ve been slowly piecing together the tools and knowledge that I’ll need to create the best version of Paint.NET ever – one that’s great both outside (for users) and inside (for developers).

Now, if you’ll excuse me, I’ve got to stop breaking things and start fixing them so that I can push out an alpha release.

I think it’s best to quote a private-message between myself and Ed Harvey on the forums:

I’ve got to stop breaking things before I start fixing them …

Paint.NET v3.5 is turning out to be more work than I originally anticipated! What started out as a “simple” rewrite of the selection rendering system has turned into a major refactor of large portions of the code base. I’m done a wholesale adoption of WPF’s mathematics primitives such as Point, Rect, Int32Rect, Vector, Size, and Matrix. These classes do a better job and are more consistent than GDI+’s Point, PointF, Rectangle, RectangleF, Matrix, etc. (I’m still befuddled as to why System.Drawing.Drawing2D.Matrix, which is six floats and 24 bytes, needs a Dispose() method. Give me a struct please.)

The goal is to make sure that the entire data flow from the selection tools to the selection renderer is as performant as possible. Right now rendering performance is not favorable compared to Paint.NET v3.36, but it’s steadily improving and there’s a lot of tricks left up my sleeve.

Speaking of WPF, I’m not using it for the UI, although I’ve been learning a lot more about it. I’m starting to come up with devious and evil plans for how I can use it a lot more in the future. I’m also realizing that a lot of the current codebase is doing things “the very hard way”, and that certain ideas implemented across multiple files and tens of lines of code can often be expressed in just 1 or 2 lines of XAML.

Oh, but I am using WPF for the About dialog. It was a good exercise and learning experience 🙂

I fixed the “can’t move a small selection” bug. The mouse input system for tools now uses double-precision floating point throughout, instead of integers. The problem here was that the tools were getting truncated mouse coordinates and even if you were zoomed in, and your 2×2 pixel selection was filling your whole monitor, you still couldn’t move the selection around in an intuitive way because the Move tool only got integers describing the mouse position in terms of image coordinates.

Tablet PC “ink” and “pressure” support is out. It was implemented in a very bizarre way and was seriously preventing further progress and bug fixes. I haven’t had any hardware to test this for at least 3 years, so it has always been a best-faith feature. Hopefully it will make a comeback.

I’m itching to release something to the public. Maybe I should start putting up daily/weekly builds on the forum, even if just to get more testing done on the install and update code path. I’ve got a small private crowd of testers on the forum, and they’re a big help, but some fresh eyes would be useful.

I’ve also finished what I hope are my last round of “edits” or “drafts” on Paint.NET’s functional and asynchronous programming models. They both revolve around a base type called Result<T>, which is an implementation of the “either” monad specialized for values and errors. Here’s a simplified version:

public class Result<T>
{
    public T Value { get; }
    public bool IsValue { get; }
    public Exception Error { get; }
    public bool IsError { get; }
    public bool NeedsObservation { get; }
    public void Observe();
}

You see, it’s always bugged me (more so recently) that in C# every method signature implicitely has a “I might throw an exception” tag on it. To borrow some C++ syntax:

public delegate TRet Func<T1, TRet>(T1 arg1) throw(…); // jee golly, I might throw! or not!

There’s no way to specify “nothrow” and have the compiler statically enforce it. Because of this, every asynchronous programming model I’ve seen has its own special way of communicating things like success, aborted, canceled, or that an exception was thrown. The documentation never seems to be clear what happens if your callback throws an exception in its guest environment. It’s such a shame. Instead, let’s start with Func.Eval which helps us to normalize the situation:

public static class Func
{
    public static Result<TRet> Eval(Func<TRet> f)
    {
        TRet value;

        try       
        {
            value = f();
        }

        catch (Exception ex)
        {
            return Result.NewError<TRet>(ex);
        }

        return Result.New<TRet>(value);
    }
}

In order to support “Eval” for Action delegates, Result<T> actually derives from a base Result class, which omits the Value and IsValue properties.

If a Result contains an error, then it must be observed. Put simply, you must either call Observe() or access the property getter for the Error property. Otherwise, once the Result instance is finalized by the garbage collector it will throw an exception, crash, and then burn. This ensures that no exceptions get lost or eaten. Also, when creating a Result that contains an error, the current stack trace is captured. This has already helped me a lot in debugging!

This whole system snakes through a few namespaces and DLL’s, and has undergone several waves of refactoring. I’m actually using all of it, so any clumsiness or impedance mismatch with the method overload resolution in the compiler is quickly caught and dealt with.

Oh, I mentioned that this ties into asynchronous programming as well. I’ll go into that in more detail later, but I’ve now got a very natural programming model for continuation-passing style which 1) makes it trivial to write sequences of code that “hops” between threads (think loading/computing in background and updating UI in foreground), and 2) doesn’t require any locks or mutexes to use (the implementation uses them), and 3) is almost as natural to use as synchronous code ala Func.Eval().

It’s also served as the basis for what is now a trivial implementation of iterative tasks. I mentioned these briefly in an older blog post. It’s a clever hack that many people have developed independently whereby you “yield” instructions to a dispatcher to perform things like switching to another thread or doing efficient waits on other objects. Combine this with a data / task parallel library like what’s coming in .NET 4.0, and we’ve finally graduated to the toddler stage of concurrent programming.

I’ve had some reports that installing the Windows Vista SP2 beta (or “CPP”) breaks Paint.NET v3.36.

You’ll get an error message like so:

Contrary to the error, Paint.NET v3.36 does not require .NET Framework 3.5 SP1.

There are two ways to fix this:

1. Install .NET Framework 3.5 SP1. I recommend doing this anyway, because it has numerous fixes and performance improvements that make Paint.NET happy.

2. Go to the directory you installed Paint.NET, and remove all the files with the “.exe.config” extension. This will un-confuse the .NET loader stuff.

This seems to be something related to the .NET Client Profile, although I’m not sure what the root cause is. I’ll be reporting this bug to the right people, so that it can be fixed.

The very cool thing about Paint.NET v3.5 is that it installs quite fast on a fresh Windows XP SP2 machine. And that includes the installation of prerequisites like Windows Installer 3.1 and the Client Profile version of the .NET Framework 3.5 SP1. Even on my new little Atom 330 box* it is kind of pleasantly fast. I’d even say it’s fun. (The unfortunate thing is that Paint.NET v3.5 is not yet out of “pre-alpha” …)

Intel BOXD945GCLF2 Atom 330 Mini ITX Motherboard/CPU Combo Intel BOXD945GCLF2 Atom 330 Intel 945GC Mini ITX Motherboard/CPU Combo

Once you jump over to Windows Vista, the story becomes very very very very dire. It took a full hour to install .NET 3.5 SP1. The hard drive was thrashing and yelling the entire time, and CPU usage was quite high. In the middle of this, a Windows Update dialog popped up in the corner telling me I needed to restart. That sounds like a bad idea since I’m still in the middle of installing a new system component! This paints a very bleak picture for getting .NET 3.5 SP1 and Paint.NET v3.5 successfully deployed to the large userbase that I have currently sitting on .NET 2.0 and Paint.NET v3.36. I’m afraid that most users will see the .NET installer “hanging” at 40% and just restart their computer, or cancel it, or kill it using Task Manager. How fun will it be for users to click on “Install Update” only to have to wait an hour before they can use their computer again, let alone Paint.NET?

I honestly don’t think it’s worth 1 hour to install a 2 MB program. Even Adobe Photoshop and Mathematica 7.0 install in minutes, and they are hundreds of megabytes.

This isn’t a random or one-off occurrence — this is not the first time I’ve seen this. Almost every time I’ve installed .NET 3.5 SP1 on to any system, whether it’s mine or someone else’s, the same thing happens. It doesn’t matter if it’s an Atom or a brand new 3.0GHz Core 2 Duo, it still takes one full hour. Sometimes you can actually get the installation to complete quickly if you go and make sure that Windows Update is completely caught up. Even then, you can never be completely sure. Any system that isn’t used 8+ hours/day by a computer-industry professional like myself is likely to be at least 1 update behind. (I’ll bet a Core i7 965 could do it in 45 minutes though :))

This is very frustrating, to say the least. On the positive side I know some of the people who work on this stuff, and they’re all great people who want things to be awesome. You can be sure I’ll be e-mailing them soon 🙂 And with any luck, the “GDR” update that’s coming (soon?) will have already fixed this. Cross your fingers.

Performance of the Atom 330 is actually surprisingly good. The results of 32-bit PdnBench are almost exactly the same as a Pentium 4 3.0 GHz “E” Prescott chip — about 180 seconds for completion — which is impressive to say the least. Back in the day (2004) that P4 chip consumed so much power that some reviewers melted their motherboards, whereas this Atom barely even needs a heatsink. In 64-bit mode, the Atom 330 pulls ahead to 155 seconds. Those results use 2 threads on the P4 (single core w/ HyperThreading), and 4 on the Atom (dual core w/ HyperThreading).

* Actually it’s not really a box. It’s small, and not inside of a case. Maybe “kit” would be a better term?

** Yes, I’m testing out some newegg.com affiliate stuff. If you’re interested in the Atom 330 board listed above, then please click on the “Buy” button above. Just like Amazon affiliate links, if you buy it via that link then I get a tiny amount of the purchase price. It doesn’t cost you anything extra. It’s another way to support Paint.NET 🙂

Sadly, I fried my Pentium 4 test system a few days ago, which had proven invaluable in my performance testing of Paint.NET v3.5. I went to turn it on* and the screwdriver missed by a few millimeters, shorted the wrong pins, and … bzzzt. No more P4.

* Since this system was “bread boxed,” meaning that it wasn’t inside of a case or anything, turning it on involved shorting the two pins that the power button is normally wired directly straight to.

Fortunately I have one of these on the way from newegg. Along with twenty dollars worth of RAM (2 GB), I will soon have a new performance test bed.

It’s a motherboard with a soldered-on Intel Atom 330 CPU for $80. It’s dual-core, supports 64-bit, and has HyperThreading. And it runs in a small 8W power envelope (well, the CPU itself anyway).

Think about it: for $80 you can get started with a system that supports 4 hardware threads! I will probably disable the second core and HyperThreading, as my primary purpose is low-end, single-core performance testing. It will be interesting to see how the Atom scales with HyperThreading and the second core turned on.

My main complaint is that this motherboard only has VGA output: DVI is not an option. For what I’m using it for, this won’t matter, but it certainly prevents me from recommending it to others, especially for HTPC / Media Center systems.

Maybe in a few months I’ll be able to purchase a Dual Xeon based on the Nehalem/Core i7 architecture. 2 chips, 8 cores, 16 threads … we’ll pit it against the Atom and see who wins 😉

Brad Wolff recently wrote a comment on my earlier post, “Change of plans – here comes Paint.NET v3.5” :

“Rick – You mentioned that 3.5 will have “Improved rendering quality when zoomed in”. Can you elaborate on this? My fear is that we will end up having to look at the blurred mess that Windows Picture Viewer displays when zoomed in. Please tell me I am wrong!” — Brad Wolff

Brad, you’re wrong 🙂 And it’s in a good way. Paint.NET v3.5 does not use bilinear or bicubic resampling when zooming in, which is the cause of the blurred mess that you mention in Windows Picture Viewer. In fact, it is now using the same resampling algorightm for zooming in that has been employed for zooming out: rotated grid supersampling. The old resampling method was the simple nearest neighbor one. It was very fast, especially when paired with a lookup table for avoiding a per-pixel division operation. The image quality problem with nearest-neighbor is very apparent between 101% and 199% zoom levels: you end up with a moire of 1-pixel wide and 2-pixel wide samples and it just looks awful. With supersampling, we are able to achieve a smoothed look that does not blur as you zoom in.

Here’s an example from Paint.NET v3.36, where I’ve drawn a normal circle and some scribbles with the paintbrush tool. The zoom level was then set to 120%:

Here’s the same, but in Paint.NET v3.5:

At this zoom level, each pixel from the image should be drawn as “1.2” pixels on-screen. In v3.36, this entails drawing 4 pixels at 1-pixel width, and then a fifth pixel at 2-pixel width. Put another way, every 5th pixel is doubled in size. In v3.5, each source pixel ends up with a uniform width and the overlaps are smoothed together in a much more pleasing manner. (This is done on the y-axis as well — replace ‘width’ with ‘height’ in the preceding paragraph and it’s also true.) It will still maintain a “pixelated” appearance as you continue zooming in, which is what you want, but the edges between samples will look smoother.

This does come at a performance cost, but I believe it’s worth it. It also scales well with multiple cores, so it’s something that will be faster with each new CPU upgrade. I’ve also experimented with using bilinear and bicubic resampling — it’s fun, but too expensive and blurry. You would need an 8-core system for it to be comfortable.

Fluent programming gets a bad reputation, since some developers like to write code like the following:

var time = 7.Days().Plus(4.Hours())

Barf. However, when used properly, I think it’s very powerful. Let’s look at a typical method with some parameter validation:

// Copy src[srcOffset, srcOffset + length) into dst[dstOffset, dstOffset + length)
public static void Copy<T>(T[] dst, long dstOffset, T[] src, long srcOffset, long length)
{
    if (dst == null)
        throw new ArgumentNullException(“dst”);

    if (src == null)
        throw new ArgumentNullException(“src”);

    if (dstOffset + length > dst.Length || dstOffset < 0)
        throw new ArgumentOutOfRangeException(
            “dst, dstOffset, length”,
            string.Format(“dst range is not within bounds, ({0} + {1}) > {2}”, dstOffset, length, dst.Length));

    if (srcOffset + length > src.Length || srcOffset < 0)
        throw new ArgumentOutOfRangeException(
            “src, srcOffset, length”,
            string.Format(“src range is not within bounds, ({0} + {1}) > {2}”, srcOffset, length, src.Length));

    if (length < 0)
        throw new ArgumentOutOfRangeException(“length”, “length must be >= 0, ” + length.ToString());

    for (int di = dstOffset; di < dstOffset + length; ++di)
        dst[di] = src[di – dstOffset + srcOffset];
}

That’s a lot of code for parameter validation, but in a robust system it is necessary. For debugging purposes, having all the information in there with the actual parameter values is invaluable, so that you can get a stack trace that tells you, “Length was too big. It was 50, but the max was 49.”

The problem here is twofold. One, code like this gets sprinkled all over the codebase of a large application and so it gets repetitive, tiresome, and is a bug hazard. Having an off-by-1 error is many times worse if it’s in your validation code. Or, because it’s tiresome, sometimes there just won’t be any validation.

The second problem is actually much more subtle. Ask yourself this: if both src and dst are null, what exception does the caller get? (and subsequently, what goes into the crash log or Watson upload?) It will only tell you that dst is null. This leads to more iterations in debugging than is optimal, where you fix the problem of dst equaling null only to immediately get it crashing on you again when src is null. If the exception told you about both errors, you could have saved a lot of time.

This happens more often than I’d like when debugging issues on other people’s systems, especially ones I don’t have any direct access to (physical or remote, ala Remote Desktop). The end-user will post a Paint.NET crashlog to the forum, I’ll fix it and send them a patch or new build, and then the same method will crash on the very next line of code. This is especially relevant to methods for graphics which take parameters for stuff like width, height, location, bounding box, etc. The X value may be bad, but the Y value might also be bad. I need to know about both, along with the valid ranges (and not just “out of range”).

There are times where I have fixed issues with no direct interaction with a user: if I get a bunch of crash logs for a certain issue, but I can’t reproduce it, I have often been able to fix it by incorporating a hopeful and conservative fix into the next release and then monitoring to make sure that no more crash logs come in. And yes, I’ve done that many times with Paint.NET.

Reporting an aggregated judgement like this is just not fun. To go the extra mile you need to create a StringBuilder, decide on the preciding exception type, manage concatenation of multiple parameter names (“sentence-ization”), etc. Like this …

public static void Copy<T>(T[] dst, long dstOffset, T[] src, long srcOffset, long length)
{
    StringBuilder sb = new StringBuilder();
       
    if (dst == null)
        sb.Append(“dst. “);

    if (src == null)
        sb.Append(“src. “);

    if (sb.Length > 0)
        throw new ArgumentNullException(sb.ToString());

    if (dstOffset + length > dst.Length || dstOffset < 0)
        …

    if (srcOffset + length > src.Length || srcOffset < 0)
        …

    if (length < 0)
        …

    if (sb.Length > 0)
        throw new ArgumentOutOfRangeException(sb.ToString());

    …
}

Boo. This is still tiresome, and creates extra objects, etc. Because of the extra work involved, this tends to be done reactively instead of proactively. Only the “hot” methods get the comprehensive logic.

I’ve come up with another method. Check this out:

public static void Copy<T>(T[] dst, long dstOffset, T[] src, long srcOffset, long length)
{
    Validate.Begin()
            .IsNotNull(dst, “dst”)
            .IsNotNull(src, “src”)
            .Check()
            .IsPositive(length)
            .IsIndexInRange(dst, dstOffset, “dstOffset”)
            .IsIndexInRange(dst, dstOffset + length, “dstOffset + length”)
            .IsIndexInRange(src, srcOffset, “srcOffset”)
            .IsIndexInRange(src, srcOffset + length, “srcOffset + length”)
            .Check();

    for (int di = dstOffset; di < dstOffset + length; ++di)
        dst[di] = src[di – dstOffset + srcOffset];
}

Yow! Ok that’s much easier to read. And here’s the kicker: if no problems are found with your parameters, then no extra objects are allocated. The cost for this pattern is only in the extra method calls.

There are three classes involved here: Validate, Validation, and ValidationExtensions. Here’s the Validate class:

public static class Validate
{
    public static Validation Begin()
    {
        return null;
    }
}

That was easy. This allows us to not allocate a “Validation” object, and its enclosed fields, until we actually encounter a problem. The presiding philosophy in code that uses exception handling is to optimize for the non-exceptional code path, and that’s exactly what we’re doing here. Here’s the Validation class:

public sealed class Validation
{
    private List<Exception> exceptions;

    public IEnumerable<Exception> Exceptions
    {
        get
        {
            return this.exceptions;
        }
    }

    public Validation AddException(Exception ex)
    {
        lock (this.exceptions)
        {
            this.exceptions.Add(ex);
        }

        return this;
    }

    public Validation()
    {
        this.exceptions = new List<Exception>(1); // optimize for only having 1 exception
    }
}

It’s basically just a list of exceptions. AddException() returns ‘this’ to make some of the code in the ValidationExtensions class easier to write. Check it out:

public static class ValidationExtensions
{
    public static Validation IsNotNull<T>(this Validation validation, T theObject, string paramName)
        where T : class
    {
        if (theObject == null)
            return (validation ?? new Validation()).AddException(new ArgumentNullException(paramName));
        else
            return validation;
    }

    public static Validation IsPositive(this Validation validation, long value, string paramName)
    {
        if (value < 0)
            return (validation ?? new Validation()).AddException(new ArgumentOutOfRangeException(paramName, “must be positive, but was ” + value.ToString()));
        else
            return validation;
    }

    …

    public static Validation Check(this Validation validation)
    {
        if (validation == null)
            return validation;
        else
        {
            if (validation.Exceptions.Take(2).Count() == 1)
                throw new ValidationException(message, validation.Exceptions.First()); // ValidationException is just a standard Exception-derived class with the usual four constructors
            else
                throw new ValidationException(message, new MultiException(validation.Exceptions)); // implementation shown below
        }
    }
}

The sum of these collections allows us to write validation code in a very clean and readable format. It reduces friction for having proper validation in more (or all? :)) methods, and reduces the bug hazard of either incorrect or omitted validation code.

Missing from this implementation, and other kinks to work out:

• Could use lots of additional methods within ValidationExtensions. (some were omitted for brevity in this blog post)
• Calling ValidationExtensions.Check() is itself not validated. So, if you forget to put a call to it at the end of your validation expression then the exception will not be thrown. Often you’ll end up plowing into a null reference and getting a NullReferenceException, especially if you were relying on ValidationExtensions.IsNotNull(), but this isn’t guaranteed for the other validations (esp. when dealing with unmanaged data types). It would be simple to add code to Validation to ensure that its list of exceptions was “observed”, and if not then in the finalizer it could yell and scream with an exception.
• The exception type coming out of any method that uses this will be ValidationException. This isn’t an issue for crash logs, but it is for when you call a method and want to discriminate among multiple exception types and decide what to do next (e.g., FileNotFoundException vs. AccessDeniedException). I’m sure there’s a way to fix that, with better aggregation, and (hopefully) without reflection.
• Should probably change the IEnumerable<Exception> in Validation to be Exception[].

Here’s the implementation of MultiException, as promised in the code above. And, in fact, it’s incomplete because it does not print all of the exceptions in a ToString() type of call. Umm … how about I leave that as an exercise for the reader? 🙂

[Serializable]
public sealed class MultiException
    : Exception
{
    private Exception[] innerExceptions;

    public IEnumerable<Exception> InnerExceptions
    {
        get
        {
            if (this.innerExceptions != null)
            {
                for (int i = 0; i < this.innerExceptions.Length; ++i)
                {
                    yield return this.innerExceptions[i];
                }
            }
        }
    }

    public MultiException()
        : base()
    {
    }

    public MultiException(string message)
        : base()
    {
    }

    public MultiException(string message, Exception innerException)
        : base(message, innerException)
    {
        this.innerExceptions = new Exception[1] { innerException };
    }

    public MultiException(IEnumerable<Exception> innerExceptions)
        : this(null, innerExceptions)
    {
    }

    public MultiException(Exception[] innerExceptions)
        : this(null, (IEnumerable<Exception>)innerExceptions)
    {
    }

    public MultiException(string message, Exception[] innerExceptions)
        : this(message, (IEnumerable<Exception>)innerExceptions)
    {
    }

    public MultiException(string message, IEnumerable<Exception> innerExceptions)
        : base(message, innerExceptions.FirstOrDefault())
    {
        if (innerExceptions.AnyNull())
        {
            throw new ArgumentNullException();
        }

        this.innerExceptions = innerExceptions.ToArray();
    }

    private MultiException(SerializationInfo info, StreamingContext context)
        : base(info, context)
    {
    }
}

Currently, the minimum version of Windows that Paint.NET will run on is XP SP2. Unfortunately, it’s starting to show it’s age and it’s making a big hassle for the installer. The issue is that a “fresh” installation of XP SP2 does not have Windows Installer 3.1, whereas XP SP3 does. I have all sorts of custom code to detect this, and special packaging rules for creating my ZIP files and self-extractors. It adds about 2MB to the Paint.NET v3.5 download, although it greatly improves the user experience and reduces friction for getting our favorite freeware installed. I was hoping to get the .NET 3.5 Client Profile installer to auto-download Windows Installer 3.1, but unfortunately it has a hard block on this before it even starts to parse the Products.XML file which contains the installation manifest and logic.

If I were to set the minimum system requirement to be XP SP3, then it would greatly simplify things!

There’s no charge to upgrade from XP SP2 to XP SP3. So, why isn’t everyone using it yet? I have a thread over on the forum where I’m asking any XP SP2 users to reply and tell me why they haven’t upgraded to XP SP3 yet. So far the reasons are: dial-up, too busy, and “didn’t see a reason to.” (actually that last one came to me via a private message, so you won’t see it on the forum)

I’d like to extend the discussion to this blog: if you haven’t upgraded from XP SP2 to XP SP3, please post a comment and let me know why. I’m not trying to make judgements here, so please don’t be shy — I’m simply on a fact-finding mission. The sooner I can bump up the minimum requirement to XP SP3, the better things will be: the download size will go down, I can spend more time on other engineering tasks, less time testing, and I can drink more beer. All three of these make someone happier.

This also brings to light the issue of prerequisite management on Windows, and for freeware apps. First, why isn’t it easier to deal with prerequisite OS components? Second, in the eyes of a typical user, what leverage or authority does a 1.5MB freeware (Paint.NET) have in dictating what service pack level you should have installed? If Photoshop were to require SP3, you can bet that a user who just paid $650 is going to install it so that they can get their money’s worth! And it probably isn’t a good idea (or feasible!) for Paint.NET to auto-download and install an entire service pack. Which means that the user experience involves the trusty message box that says, “You don’t have ___insert stupid computer nerd babble here___. Click Yes to do something even more confusing, or No to go back to what you were doing before.”

I’m going to pick on a post that I saw on the forum recently, “Root kits for .NET framework been found” [sic]. Now, I believe this person was just doing due diligence and reporting something they thought might honestly be important. So, “sharpy” (if that is your real name!), this is not meant as a dig on you. The post points to another forum discussion at dslreports.com, which then has some other links I’ll let you explore yourself.

In short, the author of some paper or exploit is claiming they have hacked the .NET Framework such that they can bypass strong-name validation, or replace code in mscorlib.dll, etc. I’ll publish the first line of the first reply to the post on dslreports:

“The ‘exploit’ starts with the modification of a framework dll (assembly) from outside the runtime using administrative privileges.”

Spot the refutal? I put it in bold 🙂 It’s like Raymond Chen has blogged about on at least one occasion:

“Surprisingly, it is not a security vulnerability that administrators can add other users to the Administrators group.”

Here’s a pop quiz. If you have administrator access to someone else’s machine, which of the following would you do?

1. Format the hard drive.
2. Steal data, then format the hard drive.
3. Display a dialog box saying, “Gotcha!”, and then format the hard drive.
4. Decompile mscorlib.dll, inject extra code into the IL for the Assembly.Load() method, recompile the new IL into a new mscorlib.dll, replace the existing mscorlb.dll with your hacked version, edit the system configuration to bypass verification, remove the optimized “NGEN” version of mscorlib.dll, delete the pertinent log entries to cover your tracks, and then wait an undetermined amount of time to see that someone launching Paint.NET or their NVIDIA Control Panel gets a formatted hard drive instead.

 
“When the looting begins remember to consider the weight/value ratio. Here we have a few examples of high value, low effort.” http://www.safenow.org

I don’t know about you, but I’d probably just go with #1 or #3. I have all the data I need already, thankyouverymuch. No need to take a graduate course in compilers in order to do the job via #4.

Everything being done in #4 is possible for someone with administrator privilege. They’re only doing what they already have access to do. However, if a non-administrator can do this, then it’s an elevation of privilege issue. If it’s trivial to trick or mislead an administrator into doing it, then it could be called an “admin attack”. But all this is a discussion for another time.

So in conclusion, I wouldn’t be worried about this. The moment you see something about an attack or exploit requiring administrator privilege, or in some cases even just physical access, feel free to relax. (After all, if you have physical access to the computer, just hit the reset button and install Linux, right?)

* Disclaimer … Note that this is a slightly cynical post, and it’s by no means comprehensive.