Steve Hawley

Please Don’t Mind the Dust

Thu, 19 Jan 2012 10:52:58 GMT

Atalasoft is moving the blogs to new hosting software. In the meantime, here are a few favorites of mine from the past:

DotPdf: Making Your Own Shapes

Mon, 23 Jan 2012 12:20:33 GMT

One of the main ways of creating page content in DotPdf is to use shapes. We give you a number of “canned” shapes that are very easy to work with (circle, rectangle, path, text, etc.), but you will probably need to make your own shapes at some point. This article is going to show you one way to do that that is very easy.

Let’s say that you need to create a letterhead that needs to have a donut in the logo. You could just draw the donut directly, but let’s say that you’re trying to create a whole corporate presence around donuts and you need to draw a lot of donuts in a lot of places. The way to do that is to make a shape.

What is a donut? It’s two circles of different radii drawn at the same center with a fill color and an outline color. Great – these feel like things to pass to the constructor and for some properties. We’ll start by making a Donut class that is a subclass of PdfBaseShape:

using System;

using System.Drawing;

using Atalasoft.PdfDoc.Generating.Shapes;

using Atalasoft.PdfDoc.Generating;

using Atalasoft.PdfDoc.Geometry;

namespace DonutShape

    [Serializable]

    public class Donut : PdfBaseShape

        public Donut(PdfPoint center, double innerRadius, double outerRadius, IPdfColor outlineColor, double linewidth, IPdfColor fillColor)

            : base(outlineColor, linewidth, fillColor)

            Center = center;

            OuterRadius = outerRadius;

            InnerRadius = innerRadius;

        public Donut(PdfPoint center, double innerRadius, double outerRadius)

            : this(center, innerRadius, outerRadius, PdfColorFactory.FromColor(Color.Black), 1.0, PdfColorFactory.FromColor(Color.Brown))

        protected override PdfBaseShape CloneInstance()

            return new Donut(Center, InnerRadius, OuterRadius); // colors will get set by the base class

        protected override void DrawShape(Atalasoft.PdfDoc.Generating.Rendering.PdfPageRenderer r)

            throw new NotImplementedException();

        public PdfPoint Center { get; set; }

        public double OuterRadius { get; set; }

        public double InnerRadius { get; set; }

In this case, I made two constructors, one that takes the line color, line thickness and fill color and one that creates a default. Since colors and line styles are handled by the base class, we can just pass those on and forget about them for now. There are really only two pieces of work: be able to clone the shape and be able to draw the shape. Cloning is easy – just call a constructor with the center and radii. Drawing is also easy, but let’s concentrate on that code on its own:

protected override void DrawShape(Atalasoft.PdfDoc.Generating.Rendering.PdfPageRenderer r)

    PdfCircle outer = new PdfCircle(Center, OuterRadius, OutlineColor, Style.Width, FillColor);

    PdfCircle inner = new PdfCircle(Center, InnerRadius, OutlineColor, Style.Width, PdfColorFactory.FromColor(Color.White));

    outer.Render(r);

    inner.Render(r);

In this routine, I create two circles, one for the outer circle and one for the inner. The outer I create with the Donut’s line and fill properties. The inner I do the same except that the fill I set to white. I can try it out with the following test code:

PdfGeneratedDocument doc = new PdfGeneratedDocument();

PdfGeneratedPage page = PdfDefaultPages.Letter;

doc.Pages.Add(page);

Donut donut = new Donut(new PdfPoint(288, 400), 18, 100);

page.DrawingList.Add(donut);

doc.Save("donut.pdf");

When I run the app, I get a page that looks like this:

Hooray – that’s just what I expected! There’s a problem, though. If we draw the donut over the top of something else it will cover it up entirely, which is not what we expected:

PdfGeneratedDocument doc = new PdfGeneratedDocument();

PdfGeneratedPage page = PdfDefaultPages.Letter;

doc.Pages.Add(page);

// Add a red line from the center out

PdfPath path = new PdfPath(PdfColorFactory.FromColor(Color.Red), 8);

path.MoveTo(288, 400);

path.LineTo(500, 500);

page.DrawingList.Add(path);

Donut donut = new Donut(new PdfPoint(288, 400), 18, 100);

page.DrawingList.Add(donut);

doc.Save("donut.pdf");

The problem is clear – the inner circle is being painted white. This will cover up anything under it. In fact, we depend on that to cover up the brown donut. The solution is to change our approach. Instead of using two PdfCircle shapes, we’re going to use one PdfPath shape to represent both circles. A path is a collection of operations that include move, draw line, draw Bezier curve, close the path. The really cool thing is that a path can contain any number of possibly disjoint subpaths, so two circles are easy. To start off with, we need a routine that give a PdfPath shape will add in a circle composed of Bezier curves. To do this, I’ll break this out into a new method. The code presented here is based on an article by Don Lancaster. If you want to learn a great deal about the math behind Bezier curves, this is a great place to start.

protected override void DrawShape(Atalasoft.PdfDoc.Generating.Rendering.PdfPageRenderer r)

    PdfPath path = new PdfPath(OutlineColor, Style.Width, FillColor);

    MakeCircle(path, OuterRadius, Center);

    MakeCircle(path, InnerRadius, Center);

    path.Render(r);

private static PdfPath MakeCircle(PdfPath path, double radius, PdfPoint center)

    double magic = 0.551784 * radius;

    path.MoveTo(new PdfPoint(-radius, 0) + center);

    path.CurveTo(new PdfPoint(-radius, magic) + center, new PdfPoint(-magic, radius) + center, new PdfPoint(0, radius) + center);

    path.CurveTo(new PdfPoint(magic, radius) + center, new PdfPoint(radius, magic) + center, new PdfPoint(radius, 0) + center);

    path.CurveTo(new PdfPoint(radius, -magic) + center, new PdfPoint(magic, -radius) + center, new PdfPoint(0, -radius) + center);

    path.CurveTo(new PdfPoint(-magic, -radius) + center, new PdfPoint(-radius, -magic) + center, new PdfPoint(-radius, 0) + center);

    return path;

And, tada, here is our shape. The question is, why isn’t the donut hole filled? The answer is that PDF has two different ways to fill paths. The first is called the Even-Odd Rule. The PDF renderer figures out how many lines have been crossed as it goes left to right. If the number is odd, it fills. If the number is even it doesn’t. This is the default method for filling. The other method is called the Non-Zero Winding Rule. It is more complicate and has to do with the direction that lines are drawn as they cross the scanline being filled. Lines that cross bottom to top add 1 to the winding number. Lines that cross top to bottom take one away. If the winding number is non-zero, the scanline gets filled. If this circle had been filled with NZW, the center would be brown and cover up the red line.

As a final best practice rule for making reusable shapes: make shapes as generic as possible and put them into their own assembly away from the rest of your application. This will make it easier to reuse the shape in other projects and will make it more easier to reload the PDF in DotPdf for further editing.

Working with DotPdf - Shapes or Shape Generators?

Thu, 23 Feb 2012 10:18:52 GMT

DotPdf comes with a number of built-in shapes and as I mentioned in a previous blog, it’s easy to define new shapes. It’s very easy to make shapes, but sometimes we can get carried away and lose sense of what should be a shape and what should not be a shape. This blog is going to be about guidelines for categorizing your page elements and infrastructure for making large-scale document production easier.

First, let’s talk about what makes a shape. A shape should be:

Simple to represent in data (ie, you should be able to attach the [Serializable] attribute and not worry about what happens with default behaviors)
It should be blissfully unaware of the page on which it sits (or more precisely the drawing list in which it resides)
It should have absolutely no business logic

Now, let’s talk about what makes a shape generator. A shape generator can/should be:

Simple or complex in data representation (it may pull its data from elsewhere)
Aware (or unaware) of page layout
Nearly all logic (business or layout)

Let’s take an example – suppose you want to make a system to generate ebooks on the fly and you want to have page automatic page numbering. You could do that with a page number shape. It fits the categories above – for representation, you need the page number, the location on the page (but you don’t really care where). It’s pretty simple. At least it seems pretty simple, until you start considering how page numbers are laid out in reality. First, page numbers can be at the top or the bottom of the page. Second, the page numbers can be on verso (left) or recto (right) or center or alternating recto/verso. Finally page numbers can be in either Roman (upper or lower) or Arabic numerals. Phew.

This to me says that the actual page number itself is a shape, but everything around it is a generator that should be encapsulated. So let’s make that generator. First we’ll start with a few enumerations:

public enum VerticalPositionStyle

    TopRelative,

    BottomRelative

public enum HorizontalPositionStyle

    Center,

    Left,

    Right,

    Alternating

These enums will let us decide how to position the shape on the page. Now let’s think about the data that we need to represent a page number generator. We’ll need the page number, the name of the font resource, the font size, the offset from either the top or bottom of the page, the left and right margins and whether or not we are working in Roman numerals. So for this: let’s lay out some properties:

public string FontResourceName { get; set; }

public double FontSize { get; set; }

public int Current { get; set; }

public double VerticalOffset { get; set; }

public double LeftMargin { get; set; }

public double RightMargin { get; set; }

public bool IsRomanNumerals { get; set; }

public VerticalPositionStyle VerticalPositionStyle { get; set; }

public HorizontalPositionStyle HorizontalPositionStyle { get; set; }

These are all straightforward – if these were my own code for release, I would null check FontResourceName and range check FontSize at the very least, but this is sample code, so better to be brief.

Given these, we can set up a constructor:

public PageNumberGenerator(string fontResourceName, double fontSize)

    if (fontResourceName == null) throw new ArgumentNullException("fontResourceName");

    if (fontSize <= 0) throw new ArgumentOutOfRangeException("fontSize");

    VerticalPositionStyle = VerticalPositionStyle.BottomRelative;

    HorizontalPositionStyle = HorizontalPositionStyle.Alternating;

    FontResourceName = fontResourceName;

    FontSize = fontSize;

    VerticalOffset = 72 * .75;

    LeftMargin = 72.0;

    RightMargin = 72.0;

    IsRomanNumerals = false;

    Current = 1;

Again, no surprises. So how do we generate the content? For this, I broke it out very procedurally:

public virtual IPdfRenderable NextPageNumber(PdfGeneratedPage page)

    double y = GetYPosition(page);

    double[] xs = GetXStartAndEnd(page);

    PdfTextBox textBox = new PdfTextBox(new PdfBounds(xs[0], y, Math.Abs(xs[1] - xs[0]), FontSize + 2), FontResourceName, FontSize);

    textBox.Alignment = GetAlignment();

    textBox.Text = GetNumberText();

    AdvanceCurrent();

    return textBox;

In this code, I get the y position of the text and the start and end x coordinates. I make a PdfTextBox with bounds set so that the box covers the entire distance from left margin to right margin at the given y coordinate. This isn’t strictly necessary – we could just figure out where to put the text and use a PdfTextLine, but PdfTextBox will do all the alignment for us, so why sweat it? Finally, we set the text of the box, advance the page number and move on.

With the process written, we can worry about filling in the sub tasks. First – getting the y position:

protected virtual double GetYPosition(PdfGeneratedPage page)

    switch (VerticalPositionStyle)

        case VerticalPositionStyle.BottomRelative:

            return VerticalOffset;

        case VerticalPositionStyle.TopRelative:

            return page.MediaBox.Top - VerticalOffset;

        default:

            throw new ArgumentException("VerticalPositionStyle", "VerticalPositionStyle is out of range");

For this, we calculate Y based on whether it needs to be relative to the bottom or the top. Now – getting the x positions:

protected virtual double[] GetXStartAndEnd(PdfGeneratedPage page)

    double[] xs = new double[2];

    xs[0] = LeftMargin;

    xs[1] = page.MediaBox.Right - RightMargin;

    return xs;

Again, straight forward. I don’t like making the array, but I like it more than using out parameters. It’d be nice to have tuples. Now getting the alignment:

protected virtual PdfTextAlignment GetAlignment()

    switch (HorizontalPositionStyle)

        case HorizontalPositionStyle.Center:

            return PdfTextAlignment.Center;

        case HorizontalPositionStyle.Left:

            return PdfTextAlignment.Left;

        case HorizontalPositionStyle.Right:

            return PdfTextAlignment.Right;

        case HorizontalPositionStyle.Alternating:

            return (Current & 1) == 0 ? PdfTextAlignment.Left : PdfTextAlignment.Right;

        default:

            throw new ArgumentException("HorizontalPositionStyle", "HorizontalPositionStyle is out of range");

How easy! The only trick is for alternating – I use the 0 bit of the page number to determine odd/even and switch between left and right based on that. Now getting the number text and advancing the number:

protected virtual string GetNumberText()

    return IsRomanNumerals ? Current.ToRoman(false) : Current.ToString();

protected virtual void AdvanceCurrent()

    Current += 1;

For Roman numerals, I made an extension method on int that creates a string in Roman numerals from the int in either upper or lower case. I found a very nice implementation here and I wrapped it up in an extension method. I’ll post the whole thing at the end. So how does this feel when it’s put into usage? Not bad at all:

PdfGeneratedDocument doc = new PdfGeneratedDocument();

string tnr = doc.Resources.Fonts.AddFromFontName("Times New Roman");

PageNumberGenerator gen = new PageNumberGenerator(tnr, 10);

gen.IsRomanNumerals = true;

gen.HorizontalPositionStyle = HorizontalPositionStyle.Center;

for (int i = 0; i < 10; i++)

    PdfGeneratedPage page = PdfDefaultPages.Letter;

    page.DrawingList.Add(gen.NextPageNumber(page));

    doc.Pages.Add(page);

gen.IsRomanNumerals = false;

gen.HorizontalPositionStyle = HorizontalPositionStyle.Alternating;

gen.Current = 1;

for (int i = 0; i < 5; i++)

    PdfGeneratedPage page = PdfDefaultPages.Letter;

    page.DrawingList.Add(gen.NextPageNumber(page));

    doc.Pages.Add(page);

doc.Save("numberedpages.pdf");

In this code I’m making 15 pages, the first 5 are in Roman numerals, the rest in Arabic. Now as you’re reading through this code you’ll notice that all the procedural steps are protected virtual methods. Why? The answer is that by sublcassing the PageNumberGenerator you could make a number of changes that are tuned to your needs. For example, you could override the GetNumberText() method and make it look like this:

protected override string GetNumberTest()

    string num = super.GetNumerText();

    return "[" + "]";

and put each page number in a box. You could also do something much more flexible like this:

public string FormatString { get; set; }

protected override string GetNumberText()

    string text = super.GetNumberText();

    return String.Format(FomatString ?? text, text);

which would let you use any formatting text. You could set it to “Page {0} of 100”.

You could also override the NextPageNumber method and call the main code but add adornments like lines around the text or embed the page number in a colored circle.

You can see that by making careful decisions about whether a page object is a shape or comes from a shape generator, it’s easy to make very flexible code. Next time, I’ll talk about how you can generalize the shape generator concept and treat PDF generation as a process of corralling sets of page generators.

Here are the classes used in their entirety.

First PageNumberGenerator:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using Atalasoft.PdfDoc.Generating.Rendering;

using Atalasoft.PdfDoc.Generating;

using Atalasoft.PdfDoc.Generating.Shapes;

using Atalasoft.PdfDoc.Geometry;

namespace PageNumberer

    public enum VerticalPositionStyle

        TopRelative,

        BottomRelative

    public enum HorizontalPositionStyle

        Center,

        Left,

        Right,

        Alternating

    public class PageNumberGenerator

        public PageNumberGenerator(string fontResourceName, double fontSize)

            if (fontResourceName == null) throw new ArgumentNullException("fontResourceName");

            if (fontSize <= 0) throw new ArgumentOutOfRangeException("fontSize");

            VerticalPositionStyle = VerticalPositionStyle.BottomRelative;

            HorizontalPositionStyle = HorizontalPositionStyle.Alternating;

            FontResourceName = fontResourceName;

            FontSize = fontSize;

            VerticalOffset = 72 * .75;

            LeftMargin = 72.0;

            RightMargin = 72.0;

            IsRomanNumerals = false;

            Current = 1;

        public virtual IPdfRenderable NextPageNumber(PdfGeneratedPage page)

            double y = GetYPosition(page);

            double[] xs = GetXStartAndEnd(page);

            PdfTextBox textPath = new PdfTextBox(new PdfBounds(xs[0], y, Math.Abs(xs[1] - xs[0]), FontSize + 2), FontResourceName, FontSize);

            textPath.Alignment = GetAlignment();

            textPath.Text = GetNumberText();

            AdvanceCurrent();

            return textPath;

        protected virtual double GetYPosition(PdfGeneratedPage page)

            switch (VerticalPositionStyle)

                case VerticalPositionStyle.BottomRelative:

                    return VerticalOffset;

                case VerticalPositionStyle.TopRelative:

                    return page.MediaBox.Top - VerticalOffset;

                default:

                    throw new ArgumentException("VerticalPositionStyle", "VerticalPositionStyle is out of range");

        protected virtual double[] GetXStartAndEnd(PdfGeneratedPage page)

            double[] xs = new double[2];

            xs[0] = LeftMargin;

            xs[1] = page.MediaBox.Right - RightMargin;

            return xs;

        protected virtual PdfTextAlignment GetAlignment()

            switch (HorizontalPositionStyle)

                case HorizontalPositionStyle.Center:

                    return PdfTextAlignment.Center;

                case HorizontalPositionStyle.Left:

                    return PdfTextAlignment.Left;

                case HorizontalPositionStyle.Right:

                    return PdfTextAlignment.Right;

                case HorizontalPositionStyle.Alternating:

                    return (Current & 1) == 0 ? PdfTextAlignment.Left : PdfTextAlignment.Right;

                default:

                    throw new ArgumentException("HorizontalPositionStyle", "HorizontalPositionStyle is out of range");

        protected virtual string GetNumberText()

            return IsRomanNumerals ? Current.ToRoman(false) : Current.ToString();

        protected virtual void AdvanceCurrent()

            Current += 1;

        public string FontResourceName { get; set; }

        public double FontSize { get; set; }

        public int Current { get; set; }

        public double VerticalOffset { get; set; }

        public double LeftMargin { get; set; }

        public double RightMargin { get; set; }

        public bool IsRomanNumerals { get; set; }

        public VerticalPositionStyle VerticalPositionStyle { get; set; }

        public HorizontalPositionStyle HorizontalPositionStyle { get; set; }

and now RomanConverter:

using System;

namespace PageNumberer

    public static class RomanConverter

        private static int[] values = new int[] { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };

        private static string[] numerals = new string[] { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

        public static string ToRoman(this int number, bool upper)

            if (number < 0 || number > 3999)

                throw new ArgumentOutOfRangeException("number", "Value must be in the range 0 - 3,999.");

            if (number == 0) return "N";

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < 13; i++)

                while (number >= values[i])

                    number -= values[i];

                    sb.Append(numerals[i]);

            return upper ? sb.ToString() : sb.ToString().ToLower();

Finally the test code:

using System;

using Atalasoft.PdfDoc.Generating;

namespace PageNumberer

    class Program

        static void Main(string[] args)

            PdfGeneratedDocument doc = new PdfGeneratedDocument();

            string tnr = doc.Resources.Fonts.AddFromFontName("Times New Roman");

            PageNumberGenerator gen = new PageNumberGenerator(tnr, 10);

            gen.IsRomanNumerals = true;

            gen.HorizontalPositionStyle = HorizontalPositionStyle.Center;

            for (int i = 0; i < 10; i++)

                PdfGeneratedPage page = PdfDefaultPages.Letter;

                page.DrawingList.Add(gen.NextPageNumber(page));

                doc.Pages.Add(page);

            gen.IsRomanNumerals = false;

            gen.HorizontalPositionStyle = HorizontalPositionStyle.Alternating;

            gen.Current = 1;

            for (int i = 0; i < 5; i++)

                PdfGeneratedPage page = PdfDefaultPages.Letter;

                page.DrawingList.Add(gen.NextPageNumber(page));

                doc.Pages.Add(page);

            doc.Save("numberedpages.pdf");

I Like the 80s with Struct Style

Fri, 04 May 2012 14:06:48 GMT

In this article, I’m going to talk about 80s era file formats and ways you can support them in .NET and keep your code sane, safe, and short, but to start, let’s talk about data file formats and why they are the way they are or were the way they were.

First, let’s consider why we even have data files. Persistence of data is one reason, but historically you would frequently see data files built because you couldn’t keep the entire dataset in memory. In the dim dark ages, you were lucky if you had virtual memory (I’m looking at you, Macintosh System 6 and earlier) or if it was lousy (I’m looking at you Windows 3.1 and earlier), so you would try to keep your memory footprint low. The obvious solution is to dump things to a temporary file then read them back in later when you needed them again. The trick is that you want to incur as little overhead as possible, so your reading and writing code had to be simple. A typical data structure might look like this:

typedef struct t_person {

char gender;

char age;

char firstname[14];

char lastname[16];

} t_person;

OK – that’s a quick, badly-designed structure for representing a person. So how would you write it out?

if (fwrite(somePerson, 1, sizeof(t_person), fp) != sizeof(t_person))

return FALSE; /* fail */

We like fwrite, oh yes we do. So much so that if we have an array of t_person, we might write this routine for dumping it out:

int writePeople(t_person *people, int count, FILE *fp)

{

int totalBytes = count * sizeof(t_person);

return fwrite(people, count, sizeof(t_person), fp) == totalBytes;

}

and then you think – oh dang, I didn’t write out how big the array was and then you realize that you’re filling a temp file with many heterogeneous types and wouldn’t it be better if the file was self identifying? So then you would write code like this:

int writeTag(INT32 tag, FILE *fp)

{

return fwrite(&tag, 1, sizeof(INT32), fp) == sizeof(INT32);

}

int writePeople(t_person *person, int count, FILE *fp)

{

if (!writeTag(kPersonTag, fp)) return FALSE;

if (!writeTag(count, fp)) return FALSE;

int totalBytes = count * sizeof(t_person);

return fwrite(people, count, sizeof(t_person), fp) == totalBytes;

}

and by solving a problem (forgot the array length and didn’t identify the type, I’ve created several new problems. First of, fwrite was fine to use if all I was writing was characters (this is a lie, by the way), but the moment I write a non-byte, I’m now writing the int with the implicit byte ordering of the processor running the code. That means that if the tag is 0x01020304, then on a little endian processor, you will write the following bytes in sequence: 04, 03, 02, 01, but on a big endian processor (such as a 68K), you would write 01, 02, 03, 04. This means that when you inevitably port your code from, say Windows to Macintosh, your reading code (if you use fread) won’t work. Ouch.

Why did we use fwrite again? Why did that seem like such a good idea? Well, we could write the entire data structure in one shot, one line of code. Otherwise, we would have to write code to write each element out in a platform-neutral way. You’re going to have to do that, because two things just entered the equation from C that made your life worse: some compilers take the liberty of changing your structure layout in order to make accessing the elements more efficient. So that lie back there about fwrite being fine with a struct of only characters: if your compiler inserts pad bytes, you’re writing more data than you suspect. Dang. Then, when C introduce enumerated values, they left it to the compiler to decide the data type best-suited for holding all the enumerated values. The problem is that some compilers made different decisions than others and so your struct size would be different, depending on the compiler.

At this point you realize that writing structs isn’t quite so easy, and maybe that job at the garden center is looking a whole lot nicer. Still, this gives you a little historical perspective.

Flash forward to current technologies. How can we read these 80’s era data structures into C# and not suffer. You could try to set up a struct in C# and play games with struct layout attributes and read the data in in one fell swoop, but trust me, this is not the way to go. If that was bad in the 80’s, it’s just as bad now.

Let’s make some assumptions – first, let’s pretend that our data file is in big endian order. Second, let’s assume that we already have a class has methods in it like this:

public class BigEndianReader {

public static bool Read(Stream stm, out ulong ul) { /* ... */ }

public static bool Read(Stream stm, out long ul) { /* ... */ }

public static bool Read(Stream stm, out uint ul) { /* ... */ }

public static bool Read(Stream stm, out int ul) { /* ... */ }

public static bool Read(Stream stm, out short ul) { /* ... */ }

public static bool Read(Stream stm, out ushort ul) { /* ... */ }

public static bool ReadScalar(Stream stm, Type ft, out object o)

{

if (ft == typeof(byte))

{

int b = stm.ReadByte();

if (b < 0) return false;

o = (byte)b;

return true;

}

if (ft == typeof(sbyte))

{

int b = stm.ReadByte();

if (b < 0) return false;

o = (sbyte)b;

return true;

}

if (ft == typeof(int))

{

int i = 0;

if (!Read(stm, out i)) return false;

o = i;

return true;

}

// ...

o = null;

return false;

}

This is a set of methods that handle reading in scalar types and one general routine for switching based on the type. This is very straightforward code – no surprises.

Now lets figure out how to read in an array of scalars without knowing it’s element type:

private static bool ReadIntoArray(Stream stm, Type ft, FieldInfo fi, object o)

{

Array arr = fi.GetValue(o) as Array;

if (arr == null) return false;

Type arrType = arr.GetType().GetElementType();

if (!IsScalar(arrType)) return false;

for (int i=0; i < arr.GetLength(0); i++) {

object val = null;

if (!ReadScalar(stm, arrType, out val)) return false;

arr.SetValue(val, i);

}

return true;

}

This will read in an array of scalars. How do we know that the array type is a scalar? We have a private predicate IsScalar() that tells us. It essentially checks to see if the type is byte, sbyte, short, ushort, etc.

Now this is where the fun part comes in. We write a routine to auto-populate a data structure using reflection:

public static bool ReadType(Stream stm, object o, params string[] names)

{

Type t = o.GetType();

foreach(string name in names)

{

FieldInfo fi = t.GetField(name);

if (fi == null)

throw new ArgumentException("unable to find field " + name);

Type ft = fi.FieldType;

if (IsScalar(ft))

{

object val = null;

if (!ReadScalar(stm, ft, out val)) return false;

fi.SetValue(o, val);

}

else if (IsArray(ft))

{

ReadIntoArray(stm, ft, fi, o);

}

In this routine, we pass in a Stream, an object, and a list of names of fields to be populated. We could also use properties if we wanted, but I’m sticking with fields right now. With all this in place, let’s set our stage for parsing data from TrueType fonts. Keep in mind that these structures are purely representational and are not part of a good API since the abstraction is wrong. Here is a class that represents the TrueType font header structure:

class TTFontHeader {

public uint TableVersion;

public uint FontRevision;

public uint CheckSumAdjustment;

public uint MagicNumber;

public ushort Flags;

public ushort UnitsPerEm;

public long Created;

public long Modified;

public short XMin;

public short YMin;

public short XMax;

public short YMax;

public ushort MacStyle;

public ushort LowestRecPPEM;

public short FontDirectionHint;

public short IndexToLocFormat;

public short GlyphDataFormat;

public static TTFontHeader FromStream(Stream stm)

{

TTFontHeader fh = new TTFontHeader();

if (!BigEndianReader.ReadType(stm, fh, "TableVersion", "FontRevision", "CheckSumAdjustment", "MagicNumber", "Flags",

"UnitsPerEm", "Created", "Modified", "XMin", "YMin", "XMax", "YMax", "MacStyle", "LowestRecPPEM",

"FontDirectionHint", "IndexToLocFormat", "GlyphDataFormat"))

throw new Exception("unable to read TTFont header");

return fh;

}

Now I’ve got very simple code to read in all the fields. Just to remind you of the hell of the 80’s, recall that for any given data structure you may have different versions. For example, the OS/2 metrics table inside TrueType files may include more fields depending on the version. We can work with that by writing code like this:

public static TTOS2WindowsMetrics FromStream(Stream stm)

{

ushort version = 0;

if (!BigEndianReader.Read(stm, out version))

throw new Exception("failure reading OS/2 version");

TTOS2WindowsMetrics met = new TTOS2WindowsMetrics(version);

string[] names = null;

switch (version) {

case 0: names = _v0FieldNames; break;

case 1: names = _v1FieldNames; break;

case 2: case 3: case 4: names = _v2and3and4Fields; break;

default: throw new Exception("unexpected OS/2 metrics version");

}

if (!BigEndianReader.ReadType(stm, met, names))

throw new Exception("failure reading OS/2 metrics");

return met;

}

One of the reasons why I like this is that it will fail fast if you rename fields (you unit tested that, right?) and should be highly round-trip testable which should make it easy to catch missed values, typos in strings and so on. Again, this example uses fields for all the data values. This is a decision to model the C structures as directly as possible. They could very easily have been properties or the code code be extended to handle either. When you build appropriate small tools, you can build robust higher level tools for making the mundane easier to do.

Dragon Curve

Mon, 07 May 2012 14:46:56 GMT

I was looking at the code for the Dragon Curve and it struck me that this should be an easy fractal to represent in PDF. Even though the curve is usually represented with relative moves and turns which are trivial in PDF, I chose to stay closer to some of the examples in Rosetta Code to keep it consistent with their examples, if you wanted to side-by-side them. This is a great basic example on how to use DotPdf for generating graphics on a page.

The first thing was a class that wraps the Dragon curve code. There is one main entry that returns a PdfPath that represents the curve. You could parameterize it further by exposing length and split.

public class Dragon

{

private static double _sqrt2 = Math.Sqrt(2.0);

private PdfPath _path;

private double _angle;

private PdfPoint _currPoint;

private void Turn(double degrees)

{

_angle += degrees * Math.PI / 180.0;

}

private void Forward(double length)

{

_currPoint = _currPoint + new PdfPoint(Math.Cos(_angle) * length, Math.Sin(_angle) * length);

_path.LineTo(_currPoint);

}

private void MakeDragon(double length, int split, double d)

{

if (split == 0)

{

Forward(length);

}

else {

length /= _sqrt2;

Turn(d * 45);

MakeDragon(length, split - 1, 1);

Turn(-d * 90);

MakeDragon(length, split - 1, -1);

Turn(d * 45);

}

public PdfPath MakeDragon(IPdfColor color, PdfPoint startLocation)

{

_angle = 0;

_currPoint = new PdfPoint(startLocation);

_path = new PdfPath(color, .75);

_path.MoveTo(_currPoint);

MakeDragon(400, 12, 1);

return _path;

}

All that remains is to use this class in the context of a PdfDocument. First, I make a document, then a page, then I place the output of the Dragon class on the page. One thing you’ll note is that to make the page, I use the PdfDefaultPages class which is a set of factory properties each of which generates a new page in the size and orientation indicated by its name (I could’ve said eponymous size and orientation, but then I’d get a talking to about keeping my writing accessible. Have I mentioned that I love language recently?).

static void Main(string[] args)

{

PdfGeneratedDocument doc = new PdfGeneratedDocument();

doc.EmbedGeneratedContent = false;

PdfGeneratedPage page = PdfDefaultPages.LetterLandscape;

doc.Pages.Add(page);

Dragon dragon = new Dragon();

page.DrawingList.Add(dragon.MakeDragon(PdfColorFactory.FromRgb(.8, .25, .8), new PdfPoint(250, 250)));

doc.Save("dragon.pdf");

}

Seriously, that’s it. It’s a nice short, sweet example. Download DotPdf and run the code – you get a free trial!

Wow, It’s Been Quiet

Tue, 26 Jun 2012 12:04:29 GMT

Have you heard the crickets? I’m not surprised. The one thing you can count on when the blogs run thin is that we’re very busy and that there are exciting things on the horizon. I can’t talk about those things yet, but I can tell you about another thing that’s been taking a lot of my time.

One thing you should consider when you are a software engineer is your health. Seriously. Software engineering is a sedentary job. This is unfortunate, but it is what it is. It is then your responsibility to take care of yourself. When you are in good physical condition, you are more relaxed, you sleep better, you think better, etc. But there are times when we are in crunch mode and can’t exercise, right? Nonsense. First, crunch time shouldn’t exist – I believe it is the result of poor planning. Second, if you’re under the gun, you should absolutely sleep and exercise. You’ll introduce fewer bugs.

Atalasoft has a lot of runners. We have three people who have run marathons, a couple people who are doing roller derby, and so on. Being active is part of the Atalasoft engineering culture, for sure. Last year, I did the couch to 5K program and found it worked quite well. I did the routine with two other coworkers, which was nice. This year, I did a crazy thing. I’ll fill you in, but first let me give you some background. This is my daughter, Alice:

She is a funny, energetic 9 year-old girl. She also has Down syndrome. It’s been a challenge to be a parent to a child with special needs, to say the least. Fortunately, there are organizations all around the world for helping people with Down syndrome and their families as well as their educators. In Massachusetts, we are involved with the Massachusetts Down Syndrome Congress, which has been invaluable in helping us and other families in the state. I can’t imagine trying to navigate through life without their information and guidance.

This past spring, they announced that they had secured a handful of slots in the Falmouth Road Race. The race is a highly competitive 7 mile race held in August in Falmouth, Massachusetts. The catch? Runners under their name need to raise money for the MDSC. To me this is a slam dunk. So since early March, I have been training to get my distance up to 7 miles. For me, this is no small feat. Even though I did 5K last year, I lost that in the fall and winter due to circumstances that were beyond my control. Fortunately, training has been going well and though I will not run the entire distance (I will be running .75 miles followed by .25 mile walks), I will complete the race. Currently, I’m at 5.5 miles and on my last training run, I felt that even if I had to walk mile 6, I could finish the race. This is a nice confidence-building moment. In four more weeks, I should be at the 7.5 mile distance, well-enough past the 7 mile range. Please consider donating, even if you are not a Massachusetts resident. Any donation is tax-deductible and will help parents learn to raise their children to be healthy, self-advocates as well as helping educators learn to be more effective.

The Importance of Writing Good Specifications

Tue, 10 Jul 2012 10:51:03 GMT

The message in this blog article is very simple: write good specifications. The word ‘good’ is problematic as it is terribly broad, so let’s narrow it down a little bit. A good specification is simple, clear and unambiguous and when it is impossible to avoid ambiguity, it should describe how to resolve any ambiguity. The SVG specification contains a good lesson in how to not do this, which I will talk about in detail. First, let’s talk about the various ways that can be used to specify geometrical figures.

For most geometric figures, there are multiple ways that they can be specified. For example, a line (infinite) or a line segment can be specified by two points (x₁, y₁) and (x₂, y₂). In most applications, this is convenient and compact, but let’s consider another way of representing a line:

Slope/intercept (from the formula y = mx + b, where m is the slope, Dx/Dy, and b i s the y intercept)

You should know this well from basic algebra. So we can take that and say that we will represent our line as (m, b). This is nice – it’s more compact than the four points. The problem with it is that m is undefined when the line is vertical. Oops. If we specified slope intercept, we’d need a way to deal with that. Maybe a flag that says that when the flag is true, the formula is to be interpreted as Dy/Dx and m is the x intercept. OK, that fixes that problem, but it makes the spec more complicated.

This can be used to define a line – what about a segment? How about a starting point and a length? Now our spec is (m, b, f, x₁, y₁, l). This is also ambiguous, because we don’t know which side of the point to extend the length (maybe it’s centered). You see what’s happening? Something that started relatively simply is just getting worse and worse.

Now consider the SVG specification for elliptical arcs – the parameters that define it are (rx, ry, j, large-arc-flag, sweep-flag, x, y) where rx and ry are the radii of the ellipse, j is the a rotation angle relative to the x-axis, large-arc-flag defines whether to use the large piece of the arc or the small piece, sweep-flag defines the which of two elliptical paths to select that could fit the data, and (x, y) are the end point of the arc. The start point is implicitly defined by previous path. To help you out, here is an illustration from the spec:

technically this is a correct way to describe an elliptical arc, but it is wrong in so many ways. First, it is ambiguous. I can provide an ending point and radii for which there are no solutions and if you code up the math to solve for the ellipse, you will only find out about the problem when you need to take the square root of a negative number. No worries, the spec describes what you should do in these cases, in what also turns out to be an ambiguous and overly complicated fashion. Seriously. Check it out. It requires an unnecessary wall of math which turns into a wall of code. In addition, if the start and end points are 180 degrees out of phase, there is no large arc – they’re both the same size. Which do you pick? Finally, the x-axis angle, j, is totally redundant since any shape can be contained within a transform.

To be generous, there is one and only one reason I can think of for this that it’s fairly simple to decide the two points that start and end the arc if you’re hand-coding SVG, but the other ambiguities outweigh this benefit in my opinion.

Instead, they should use the specification (cx, cy, rx, rx, q₁, q₂, cw), where cx and cy are the coordinates of the center of the ellipse, rx and ry are the radii, q₁ and q₂ are the start and end angles of the ellipse in degrees, and cw determines if the arc should be drawn clockwise or counterclockwise from q₁ to q₂. This spec is simpler to implement and impossible to get incorrect values. You could simplify it further and remove rx and ry and instead use a parent scale transform to set the radii, if you wanted.

To a certain extent, I prefer the PDF approach to representing arcs and circles: you don’t. In PDF there are only Bezier curves and the specification is very simple. While drawing a Bezier curve is also simple, it can be tricky to do it efficiently. Also, circles can’t be represented by Beziers without error. Fortunately, Don Lancaster has a great article on how to approximate circles and minimize the error. If you use Atalasoft’s DotPdf toolkit, you’ll get high-level shapes that implement this for you (as well as SVG->PDF conversion). On another day, I’ll share how I turn an elliptical arc into Beziers. In the meantime, write good specifications!

About those Enums, Java…

Tue, 09 Oct 2012 13:23:25 GMT

As you’ve seen, we’ve released a new product – JoltImage. This is our foray into the Java world of image processing, something that we’ve been contemplating for some time. I will be writing about that experience so that engineers faced with similar problems (porting .NET code to Java) might have a reference.

When I started working in Java in 1996, it was a brand new language and working in it was freeing to a certain extent. I found that compared with C or C++, I was able to write far more code with far fewer bugs that I had in the past. Having checked arrays, immutable strings, and garbage collection removed three personal sources of bugs.

One thing that it lacked was enumerations. This is something that is, IMHO, vital. The work around was declaring public final values to use or to make singletons. The problem with public finals are the lack of type safety and singletons are more heavyweight than you’d like.

Before I take a hammer to Java, let’s step back and examine the use cases for enumerations:

Cardinal values

Ordinal values

Set elements

Cardinal values are effectively atoms – symbolic names that have no particular meaningful value. Ordinals are symbols that have specific values that have meaning and may or may not have operations on those values. Set elements are either cardinal or ordinal values that need to be contained in a set and have specific set operations (intersection, union, difference, complement, member, etc.).

In Java, enums are easiest to use for Cardinal values and appear to be optimized for that. I can do the following declaration:

public enum IOPortID {

A, B, C, D;

}

In this case, I can refer to an IO port very easily by name. Terrific. Now suppose that each of the ports has slightly more meaning.

Let’s say that each of those ports is associated with a hardware address. You’d LIKE to be able to just associate the address with the symbol. That should be easy, but you can’t do that. At least not really. Instead, you have two choices, code that looks like this:

public enum IOPortID {

A, B, C, D;

final int toHardwareAddress() {

switch (this) {

case A: return 0xaba;

case B: return 0xabb;

case C: return 0xabc;

case D: return 0xabd;

default: throw new RuntimeException(“Illegal IOPortID!”);

}

	or code that looks like this:

public enum IOPortID {

A(0xaba), B(0xabb), C(0xabc), D(0xabd);

private int _value;

private IOPortID(int value) { _value = value; }

public static IOPortID fromValue(int value)

{

if (value == A._value) return A;

if (value == B._value) return B;

if (value == C._value) return C;

if (value == D._value) return D;

throw new IllegalArgumentException(“unknown hardware address “ + value);

}

Either implementation is bad. The first one might be slightly better in that I’ve decoupled the port ID value from the port ID symbol and made that particular method accessible only within the namespace. In both cases, I’ve had to put in a stack of boilerplate code which is a bad code smell. I will say that because Java does not dictate how many members you put into an enum, you could very well put in any number of scalar dimensions or references to other classes. For example, you could make an enum that encapsulates longitude and latitude and represents major cities.

And herein is the problem with Java enumerated values: they are not enumerated values. They are singleton classes. When I declare an enum as in the very first example, I end up with 4 classes constructed, A, B, C, and D. Don’t believe me? Add a setValue() method to each of the above and you can mutate your enum. Yikes. I can think of a few reasons why you might want to do this, but they’re all hacks on top of a bad base model.

One of the other handy use cases in enums is to represent bit flags for settings. This is frequently used in software – for example, the permissions in a PDF file is represented by a 32-bit integer holding a set of bit flags. The prescribed method is to use EnumSet. EnumSet has two main problems with it which are intimately entwined: it is neither blittable nor is it immutable. Let me explain – a blittable type is any type that is bit-for-bit copied by an assignment. Scalars (int, char, float, etc.) are blittable. Class instances are not blittable, they are copied. Since Enums and EnumSets are classes, they are not blittable. This means that if they are mutable (and Enums can be and EnumSets are), then we have to be very careful about how they are used. For example, if I design an abstract class that needs to return an EnumSet of all operations that it supports, I need to either prescribe that the implementation always return a new EnumSet (bad idea – I can’t trust all my implementors) or wrap each call to the abstract method in another method that does a EnumSet.copyOf(). This is cumbersome and error prone and is necessary because EnumSet is fundamentally broken. remove() and removeAll mutate the set – this is bad. Instead, their should be the methods intersect(other), union(other), difference(other), complement(), which do the actual set operations and return a new EnumSet with the appropriate types and there should be no mutators. This way instead of writing this code:

public final boolean has1DOtherThanCode39(EnumSet sym)

{

EnumSet set = EnumSet.copyOf(sym); // have to copy!

set.removeAll(Symbologies.all2D());

set.remove(Symbologies.CODE_39);

return !set.isEmpty();

}

I could write this:

return !sym.difference(Symbologies.all2D().union(Symbologies.CODE_39)).isEmpty();

or the equivalent in .NET

return (sym & ~(Symbologies.All2D | Symbologies.Code39)) != 0;

The requirement of the copyOf() is to prevent us from side-effecting the input, since it is passed by reference. This is an easy thing to forget which is a bug waiting to happen. If we left out the copyOf() call, we would be side-effecting the caller’s copy which in the case of this particular operation will not always be noticeable. Not cool. In addition, if EnumSet were immutable, then we would be allocating 3 EnumSet objects that would get thrown away immediately (probably their reason for making them mutable in the first place).

So we can see that the Java Enum is a class and not actually an enum and when any case beyond simple cardinals is needed (which in my experience is about 3/4 of the time), the programmer is required to use boilerplate code which is error prone. Finally, the use of EnumSets is cumbersome as well as requiring the client to understand the consequences of having a mutable class, although to its credit, EnumSet will scale well beyond 64 members. By contrast, the .NET enum is a scalar (and blittable), and is trivial to use in all the common cases and only starts to be a leaky abstraction when the use case is inappropriate for an enum and more appropriate for an actual class.

Don’t Do Eclipse Headless Builds Ever

Mon, 29 Oct 2012 10:46:36 GMT

We standardized on using Eclipse for Java development for a few reasons, not the least of which was the having Team Explorer Anywhere integrated. This was a key feature for us since we use TFS for our regular source control and would prefer to not have another infrastructure system, if possible.

Since our shop uses continuous integrated and have all our releases built by automation, we needed to build the Eclipse projects on our own system. If you search for “eclipse headless build” you will find a number of hits on how to do this. They work. Sometimes. Sort of. We found a couple things – we can’t check in the .metadata folder since it stores absolute paths and one particular engineer’s .metadata folder won’t necessarily work on the build machine or any other engineer’s machine. So we kept a private copy on the build server with the provision that if you added a new sub project, it would be necessary to update the .metadata folder on the build server (and on engineering machines). We found that even with that, builds were flakey. They worked most of the time, but not all the time. By adding a call to refresh the projects before the headless build, we found that we could get a more reliable build. Then we had a new project added that didn’t really change the build order on the engineering machines, but it was causing errors on the build server that didn’t halt the build. We only found out about them by reading the logs and finding out that later in the build obfuscation was failing. Interestingly enough, the java compiler was spouting errors, but was writing .class files that were technically correct but would never load or run (the compiler injected throws in all the constructors).

Long story short: Don’t Do Headless Builds with Eclipse. They may work in simple projects, but will ultimately fail in the worst possible way: generating bad code and not failing the build.

So what do we do? All our builds are run from CruiseControl which then fires up NAnt tasks. When we added Java, we kept the same infrastructure but now fire off Ant tasks to do more Java specific things. First, I broke down a project build into 5 tasks (there’s actually a 6th, but I haven’t integrated it in this build step fully yet):

validate
wipe previous output (not technically necessary, but I like to make sure the environment is clean)
compile
make jar
obfuscate

With this, I added one file to the global workspace and one file to each project. The global file is a csv that contains a project directory name on each line (with the notion that there may be other information later on each line), then I loop over it with a NAnt foreach (this implies that the file is in build order):

Then I set up some properties including the .classpath file, the src folder, the bin folder and so on.

Validation – I want to make sure that each project folder really is intended to be a project. There should be a .classpath and a file I call ProjectManifest.xml. It don’t actually contain anything yet, but in the future, there may be project specific properties set in this file so that there need not be as much logic and special cases in the actual build script.

Wipe Previous Output – this is easy, just a delete task on the bin folder.

Compile – this is somewhat complicated. I wrote an embedded C# script in NAnt that parses the .classpath file and turns it into a string suitable for a command line option to the java compiler. Here’s the code, which works well enough:

You can see that I leverage the Xml serializer to get the information that I need. My first job after writing the compile-java task was to verify that a compiler error would fail the build appropriately. It does. Here is the compile-java task:

And the actual Ant task is straight forward:

The only other missing piece is how we invoke ant:

        basedir="${Dir.Ant}\bin"
        workingdir="${Dir.Build}"
        output="${Progress.Log.File}"
        append="true"
        timeout="7200000"
        verbose="true"
        failonerror="true"
        commandline="-buildfile ${quote}${Dir.Build}\JavaImageAnt.xml${quote} ${ant.commands} ${ant.task}" />

Oh and ${quote} is used to get an embedded double-quote into a string .

Jar – jar is similar to compile. We need the bin directory to pass in and then invoke an Ant task to build the jar file. This is complicated only by the one project that has to have a few external jar’s combined into it, so one project gets handled with a special case Ant task. Every project gets a jar even though unit test projects don’t strictly need them.

Obfuscate – the obfuscation task is nearly identical. At present, all our jars get obfuscated with the same settings using Zelix Klassmaster. We skip the obfuscate step on unit tests as we don’t need them and the dependencies would be unusual.

There are a number of ways that this type of build automation could be done – for example, keeping a completely separate ant file that handles the build entirely. In an ideal world, the build would be done by the same system as an engineering workstation, but since that isn’t currently possible, we strike a balance to get the build as automatic as possible. In theory, we should be able to analyze all the .classpath files and intuit the build order and this might be a good step for the future.

What is Partial Function Application?

Mon, 19 Nov 2012 11:30:52 GMT

I’m going to talk about Partial Function Application in F# and show how you can simulate that (to a degree) in C#.

Let’s start with a function to calculate quadratic of the form ax² + bx + c:

let quadratic a b c x =
    a * x * x + b * x + c

This is pretty straight-forward – it just rips through the math and you can see that it works:

> quadratic 4.0 3.0 3.0 0.0;;

val it : float = 3.0

> quadratic 4.0 3.0 3.0 1.0;;

val it : float = 10.0

> quadratic 4.0 3.0 3.0 2.0;;

val it : float = 25.0

The cool thing is that you don’t have to pass all of the arguments in to quadratic. If you leave off arguments from the end to the front, what you get back is a function that can be applied to the arguments that you left off. What happens is that the arguments you do supply get bound to the parameter names, but the rest still need to be done. I can rework my example to save some typing:

let q1 = quadratic 4.0 3.0 3.0

> q1 0.0;;
val it : float = 3.0

> q1 1.0;;

val it : float = 10.0

> q1 2.0;;

val it : float = 25.0

Moreover, I can define other functions in terms of quadratic. For example, one form of linear function is a quadratic with a = 0:

let linear = quadratic 0.0

Nifty. Now how do we do this in C#? To do this, you need to think about what’s happening. When you invoke a function without its full complement of arguments, the compiler goes through an act called “binding” wherein the supplied argument values are permanently tied to the parameter names. In Lisp or Scheme (and F# is a cousin of these languages), this is often done by creating an “environment” which is a collection of bounds symbols and their values. We can do this by representing a function as a delegate (which contains an optional reference to a class) and using the class itself as the environment.

Here’s the quadratic code “ported” to C#:

public class Quadratic
{
    private double _a, _b, _c;
    private Quadratic(double a, double b, double c)
    {
       _a = a;
       _b = b;
       _c = c;
    }
    private Quadratic(double a, double b) : this(a, b, 0.0) { }
    private Quadratic(double a) : this(a, 0.0, 0.0) { }
    public static double Value(double a, double b, double c, double x)
    {
       return a * x * x + b * x + c;
    }
    private double _f1(double x) { return Value(_a, _b, _c, x); }
    public static Func<double, double> F(double a, double b, double c)
    {
       Quadratic q = new Quadratic(a, b, c);
       return q._f1;
    }
    private double _f2(double c, double x) { return Value(_a, _b, c, x); }
    public static Func<double, double, double> F(double a, double b)
    {
       Quadratic q = new Quadratic(a, b);
       return q._f2;
    }
    private double _f3(double b, double c, double x) { return Value(_a, b, c, x); }
    public static Func<double, double, double, double> F(double a)
    {
       Quadratic q = new Quadratic(a);
       return q._f3;
    }

}

What I’ve done is hidden the environment for the function in a private constructor for the class Quadratic. I implemented the actual quadratic function with the static method Value. In the first flavor of F, I take 3 arguments and by newing up a Quadratic, I have bound the values into the environment. _f1 only takes x as its argument and uses _a, _b, and _c from the environment to calculate the quadratic. In every subsequent flavor of F, I drop an argument.

I’m not saying that this is what F# is actually doing under the hood. There are other ways to get the same behavior, but they’re all fairly similar. For example, the F# compiler could just be writing a new function on the fly with the bound values being constants in the IL. What happens is still the same; it’s just that the individual IL instructions become the environment instead of a class object. Similarly, the code above could have used lambda expressions instead of the _f functions and then the lambda expression would have captured the arguments instead of the class:

public static Func<double, double> F(double a, double b, double c)

{
    return x => Value(a, b, c, x);

}

Looking at the C# code, you should be asking yourself why on earth you would want to do this in C#. You might want to keep in mind that class encapsulation is a way of representing closures rather than the day-to-day business logic of your application. Another case is when you have the task of porting F# code to another platform. In our managed version of dotImage, I made heavy use of partial function application in order to make it easier for me to write generic functions to operate on different pixel formats. It made my code a lot easier to read, maintain, and debug. When I ported this to Java in JoltImage, I could have written the code without using this notion. I was sorely tempted since at present Java doesn’t have delegates or lambda expressions in the way that C# does. Because of this, I made an private abstract base class that had the method I wanted to expose and then had a subclass for each pixel format that had a constructor that parameterized the environment.

Jargon

Mon, 19 Nov 2012 16:23:39 GMT

Last blog, I wrote about using C# to get some of the benefits of F# partial function application. In submitting the blog, I was asked by Rick C. about the phrase “newing up”. That got me thinking about the jargon we use day to day and how it comes to be.

When I was in high school, I did a small amount of electronics work with my dad. He introduced me to perfboard, which we used for making small circuits by using a wiring pen to make circuits – bread-boarding he called it. From that point on, I had internalized the jargon. I never really thought about it much – it was just a word. It’s kind of like how most people don’t think about the word ‘handicapped’ which derives from a lottery game called “hand in cap”. My after school job was working at Bell Laboratories for Max Mathews as a violin builder. The necks of the violins were made from glued-up pieces of poplar. Max sent me to the Bell Labs stock room with a shopping list of things I’d need. The list included “bread boards,” which I found in the stock room. They were exactly that: bread boards. Large wooden boards for rolling out bread dough and which were repurposed by electrical engineers for making prototypes. In my case, I cut them up and, after much carving and other work, turned them into the final product.

Yup, that’s me circa 1982.

And in software engineering we make up jargon all the time. We use metaphor, make up new words, and repurpose old words. We talk about visitors, enumerators, events, and so on deftly. Sometimes the origin isn’t always clear. My friend Jim Blandy was given a task to port the text editor sam and was trying to figure out some of the code. Completely out of context, he asked “Hey Steve, what’s a rasp?” I answered simply, “a file with holes in it.” This was a forehead-slapping moment which Jim no doubt punctuated with a lot of laughter. He had been trying to work out the meaning of the Rasp struct, which was intended to be a representation of a partial file – a literal file with holes.

And so we come back to the phrase “to new up”. I consulted a friend of mine who is a dictionary researcher was unable to shed deeper light on the origin of the phrase beyond the earliest I’d heard it which was in 2008, spoken by Anders Hejlsberg at the PDC 2008 conference as a substitute for the word “instantiate”. The first I saw the keyword ‘new’ in a programming language was in Pascal, but compared to a typical object-oriented implementation of operator new, the Pascal’s version is little more than syntactic sugar giving the language type-safe memory allocation. I had expected it to be an older keyword, considering that the English word ‘new’ is very old, but didn’t find earlier programming languages that use it. Heard it earlier than that? By all means, let me know.

Merry Christmas and Happy Holidays from Atalasoft

Fri, 21 Dec 2012 12:24:04 GMT

For the last several years, we’ve hosted a Secret Docubot event at Atalasoft. This year, we combined the annual Docubot festivities with a bacon day. Now as I sit back at my desk, trying to concentrate in the face of a food coma, I thought I’d present you with some pictures I took during the festivities:

Hi! I’m bacon!

We bought a grill to keep in the office. This one is much larger. It’s loaded up with two pounds of thick cut pepper bacon from Burger’s Smokehouse.

By the way, their Cajun Steak Cut bacon was awesome. See that jar there? Rick G. claims it’s moonshine. I don’t know how he got it.

Yes, that’s a donut. Yes, we eat dangerously. Just not every day.

Sadly, as delicious as it looks, it didn’t taste that great – it tasted like a hot, extra greasy donut.

Elaine and her animatronic hat.

Rick C. opening Docubot gifts.

Engineering Kevin preparing to shuffle.

Marco conferenced in.

Asia with morning coffee.

Lou recreated Eric’s tragic dodge ball accident

Eric, clearly excited to open his Docubot gift.

Yes. Yes you are.

What Does It Take To Be A Software Developer?

Mon, 07 Jan 2013 14:52:47 GMT

I saw this question on Metafilter about what CS courses are necessary to be a software developer and thought I would take the opportunity to expound a bit.

The first non-useful answer is: all of it. I went to Oberlin, a college that only grants arts degrees, and received a degree in computer science. In that time, I also took classes in religion, ethnomusicology, physics, media, anthropology, and so on. Anything that seemed interesting and I could schedule, I tried to take. I honestly believe in the value of breadth in many things and depth in a few things. The value is especially apparent in software where solutions frequently need to be tailored to the problem domain and the possible number of domains that can be addressed effectively with software grows daily. If you know about a wide number of things, you can better tailor solutions to those domains. Being a lifelong learner makes it easier to learn new problem domains.

The second answer, more useful perhaps, is the following.

An intro class in a high-level language – you’ll probably find classes taught in Java, C#, Python, Ruby, or C++. My first CS class in college was in Pascal. If you already know a HLL, it’s still worthwhile, especially if it’s a different language. In fact, you might want to look at the entire course book to see if all the classes are taught in only one or two languages. That’s a bad sign, especially for a budding software developer where you should expect to need to learn a new language every few years. I know more than 20 and it is a career skill to pick up a new one in short order.

A class in algorithms and analysis – this is probably the one that I touch on the most without ever really having to crack a book (I do keep the textbook in my office in case), just for the ability to analyze the best, worst and average cases of code I write. I have encountered code in the wild that search for the first/next instance of a string in a stream that was O(n!) – easy to spot if you know what to look for.

A class in design patterns – I don’t know if this is in any college curriculum, but when I started my professional career, there weren’t any formal design patterns. They were informal and maybe differently named from shop-to-shop. I did discover that many of us had invented the same things just to get a job done and the wise ones abstracted them just enough to be able to apply them in many circumstances while keeping them nimble (for example, I had a tight library that was built around the Visitor pattern which was the basis for an entire UI toolkit.

A class in system architecture – in my day, this was called assembly, but I believe that a good solid understanding of the hardware underneath your computer is key to making good high level decisions as well as making you a far better debugger. It is also necessary for writing a compiler.

The Scheme/Functional class – if you’re lucky, your department will have a Scheme zealot. I’ll be honest, I hated Scheme. I’m a very concrete/practical programmer by nature and Scheme drove me crazy. Not because I didn’t understand it – I did. It drove me nuts how fluffy the language was in terms for how it worked and how code I wrote would stall for chunks of time while the garbage collector went to work to get rid of all the things I allocated that I couldn’t prevent. I swear I was the worst offender of using set! and its variants in my code just to avoid wasting time/memory. Still, in spite of the structural language deficiencies, it is a fabulous language for getting you to stop thinking about problems sequentially.

A class in compilers – this was my hardest class, I think. I flunked it. But it was the most valuable class for learning how to debug a high level language from the lowest level. You should get to the point where you can look at machine generated assembly language and mentally decompile it into the HLL that made it. For example, I had a third party library that worked most of the time, but crashed at other times. It turns out that they were using C enums in size-dependent data structure and their compiler chose one size for the enum and my compiler chose a different size. Without being able to understand what a compiler would have done with code to operate on structs that contained this enum, I would’ve been dead in the water. I run into this kind of thing All. The. Time.

A class in operating systems – and by extension, this class should cover concurrency and resource management. You’re writing code and you’re running it on what now? You should understand how an operating system works, how to write device drivers, and especially concurrency. When every machine, including your phone, is shipping with a couple cores, you should understand how to best leverage concurrent programming.

Beyond that, everything else is gravy. Also consider a writing class of some kind. Clear communication is vital and it is one of the things that I use to pick a new hire.

How to Manage Temporary Files

Wed, 09 Jan 2013 14:09:30 GMT

If you’ve written software to manipulate large chunks of data, you’ve likely created temporary files to hold the data for you. And if you’re like me, your machine currently has 2587 files in your personal Temp folder. Why? Chances are there are a ton of apps on your system that are Doing It Wrong. I’m going to talk about how most apps do this, how it goes horribly wrong, and what you can do to mitigate this problem for your own code.

Most apps will get the path to the Temp folder and run a loop creating files based on time stamp or time stamp followed by iteration until they succeed in making a new file. This path (or stream) gets used in the application in some manner and at some point in the future it will get removed. And you can bet that it’s the last step where applications screw up – they don’t (or can’t) clean up after themselves.

If you’re using Path.GetTempFileName(), stop. Seriously. Just stop using it. It’s not appropriate. It tries to create a file in the form tmpXXXX.tmp, where XXXX is a 4 digit hex number. This is not appropriate for a couple reasons. First, in my own folder, there are currently 2516 files that match that pattern. In other words, 2516/65536 or 3.8% of the files are already in use and I swear I cleaned out that folder a couple months ago. In short order, it will fill up. Further, every nth call will take longer, as the first n-1 tries to make the file will fail. On top of that, there is no infrastructure to take care of the temporary file when you’re done with it. The developer is responsible for removing it and we know how well developers remember to do things.

This is a resource problem: a limited number of slots and responsibility to get and release the resource is in the hands of the developer. When you approach this as a resource problem, it becomes a whole lot harder to screw up.

So let’s set a few goals for this task. This code should be:

Easy to use
Hard to screw up
Customizable
Better than Path.GetTemporaryFile()

So let’s start with a TemporaryFile object. This is what is going to hold your information about the temporary file. There are a number of ways this could be structured to be more flexible (like a template base class wherein subclasses could be any Stream instead of a FileStream), but it’s called TemporaryFile not TemporaryStream, so let’s keep it simple. Here is TemporaryFile:

    public class TemporaryFile : IDisposable

        public TemporaryFile(string path)

            if (path == null)

                throw new ArgumentNullException("path");

            Path = path;

            TemporaryStream = new FileStream(path, FileMode.Create);

        public Stream TemporaryStream { get; private set; }

        public string Path { get; private set; }

        public override string ToString()

            return Path;

        private bool _disposed = false;

        public void Dispose()

            Dispose(true);

            GC.SuppressFinalize(this);

        protected virtual void Dispose(bool disposing)

            if (!_disposed)

                if (disposing)

                    TemporaryStream.Dispose();

                    File.Delete(Path);

                _disposed = true;

        ~TemporaryFile()

            Dispose(false);

In this case, I chose to make the class itself immutable and Disposable. As it stands you could use this class as a wrapper around the result from Path.GetTemporaryFile(), but we’ll do better than that. Remember that TemporaryFile is a resource and if that’s the case, it should be IDisposable. We want to do something very specific when the file is closed. So following the pattern in IDisposable Made E-Z, I’ve made this class do a few things: open the file on construction and on disposal dispose the TemporaryStream and delete the path. According to the spec for Stream.Close(), it is not necessary to call Close() but to instead ensure that Stream.Dispose() gets called. If either Stream.Dispose() or File.Delete() throw an exception, you probably have worse problems on your hands. If you wanted you could add an implementation of Equals and GetHashCode. I chose not to since pointer equality should be good enough.

Where possible, TemporaryFile objects should be scoped within a using() block to ensure they get disposed in a timely manner, otherwise you have to pray that the GC will help you out at the end of app life.

We’re not done yet – as mentioned before, Path.GetTempFileName() gets worse the more you use it. We can fix that too. Also the filenames it generates are not so good in that we can’t fingerprint them as our own so that we can check at a glance that we’re leaking temp files or better yet, write a unit test to take care of them. So how do you make a TemporaryFile? Use a factory:

    public class TemporaryFileFactory

        protected static string kDefaultPrefix = "Tmp";

        protected static string kDefaultSuffix = "";

        protected static string kDefaultExtension = "tmp";

        protected static int kDefaultRetries = 10;

        public static TemporaryFile MakeTemporaryFile(string extension) { return new TemporaryFileFactory(null, null, null, extension, kDefaultRetries).MakeTemporaryFile(); }

        public TemporaryFileFactory(string tempFolder, string prefix, string suffix, string extension, int retries)

            if (retries <= 0) throw new ArgumentOutOfRangeException("retries");

            Retries = retries;

            TempFolder = String.IsNullOrEmpty(tempFolder) ? Path.GetTempPath() : tempFolder;

            if (!Directory.Exists(TempFolder))

                throw new IOException(String.Format("Temporary folder '{0}' does not exist", tempFolder));

            Prefix = String.IsNullOrEmpty(prefix) ? kDefaultPrefix : prefix;

            Suffix = suffix ?? kDefaultSuffix;

            Extension = SanitizeExtension(extension ?? kDefaultExtension);

        private string SanitizeExtension(string ext)

            if (ext.EndsWith("."))

                ext = ext.Substring(0, ext.Length - 1);

            if (ext.StartsWith("."))

                ext = ext.Substring(1);

            if (ext.Length == 0)

                ext = kDefaultExtension;

            return ext;

        public string TempFolder { get; private set; }

        public string Prefix { get; private set; }

        public string Suffix { get; private set; }

        public string Extension { get; private set; }

        public int Retries { get; private set; }

        public TemporaryFile MakeTemporaryFile()

            for (int i = 0; i < Retries; i++)

                string path = GenerateTemporaryPath(i);

                if (!File.Exists(path))

                    return new TemporaryFile(path);

            throw new IOException(String.Format("Unable to create temporary file in {0} after {1} {2}.", TempFolder, Retries, (Retries == 1 ? "try" : "tries")));

        protected const string kDefaultFormat = "{0}{1}{2}.{3}";

        protected virtual string GenerateTemporaryPath(int retry)

            Guid g = Guid.NewGuid();

            string newPath = Path.Combine(TempFolder, String.Format(kDefaultFormat, Prefix, g.ToString("N"), Suffix, Extension));

            return newPath;

In this case, we’re making the factory easy to use if you don’t care about the file name format and easy to customize if you do. The first thing you should know is that I’m defining the format of a temporary file name this way – .. The defaults are such that you should get Tmp.tmp for your temporary file. There is a main constructor that takes values for Prefix and Suffix and Extension and defaults them if they are null (or in some cases null or empty). The constructor also takes a path to the folder you want to use for temporary files, but you can also set this to null and it will use Path.GetTempPath() instead. The question is, what should go in the part of the file? Why not use a GUID? Just from the definition, I’m fairly certain that I only have to check once to see if the path will exist since the GUID should be unique by definition. Still, GenerateTemporaryPath() was made virtual so you could override if this doesn’t suit your particular needs. GenerateTemporaryPath() includes a retry number, so you could reimplement Path.GetTempFileName if you wanted to (but why?). There’s some basic error checking/patching to mitigate pilot error in SanitizeExtension() and finally a nice static factory method that news up a factory for you with defaults and generates a TemporaryFile for you. Here’s my test code:

        static void Main(string[] args)

            List<string> files = new List<string>();

try

                for (int i = 0; i < 20; i++)

                    using (TemporaryFile tf = TemporaryFileFactory.MakeTemporaryFile(null))

                        files.Add(tf.Path);

                        Console.WriteLine("Created " + tf.Path);

                        if (i > 18)

                            throw new Exception("no purpose");

            catch { }

            finally

                foreach (string path in files)

                    if (File.Exists(path))

                        Console.WriteLine("error - file " + path + " still exist.");

which demonstrates how to make TemporaryFiles using the static factory method within a using and throws an exception for no other reason than to demonstrate the IDisposable does what it says on the box.

From an architecture point of view, this is good enough. It could be slightly cleaner and if I were to make any changes at all, I might put the static factory method(s) inside of TemporaryFile instead of TemporaryFileFactory, then I would call the methods Create(). If I wanted to hide the implementation details of TemporaryFile, I would probably make an interface ITemporaryStream and only put the TemporaryStream property in it. Then if you wanted to use a MemoryStream based factory you could. I think this is poor decision for a few reasons:

Temporary files are well established in the art
MemoryStreams (or other streams) don’t have the same need for a file deletion as a FileStream and fall outside of our problem domain
It would necessitate either a factory for specific file streams
Existing code isn’t always .NET Stream compatible (for example, a C library that needs a path)

So you see that by looking at the task as a resource problem rather than a temporary file problem, we can make a solution that is as easy to use and more resilient.

Being Lazy is a Virtue

Wed, 30 Jan 2013 13:18:03 GMT

One of the things that I admire in solid programmers is laziness. Some programmers will go to extreme lengths to avoid doing certain classes of work and frankly, I can’t blame them really. For example, if you need to have a set of look up tables in code from some specification, you could just pull of the spec and start typing in the tables. A clever programmer will look at the task and start asking the following questions:

How much typing will each entry in the table take (and by extension, how long will the whole task take)?
How many mistakes will I make just typing?
How long will it take to find all of them?
How long will it take to fix all of them?
How irate will my customers get because of 3 and 4?

When 1 gets measured in any units greater than ‘minutes’ and 3 gets measured in units of days to years, a very clever programmer will also ask, “how can I automate this?”

This week I was looking at creating a number of tables (22 in all), each of which had somewhere around 200 entries in them. That’s around 4000-4800 entries to type in. Yuck. That’s easily 3 days of typing and the number of mistakes would probably be about 10%, which would easily be another day to catch 95% of those errors and weeks for the rest.

Enter the robot.

First trick, look at your source data and see if you can easily parse it. For example, I needed to parse Adobe Font Metrics files and the spec is blissfully simple. It’s mostly a collection of one key/value pair per line as well as a set of separately subsection with differently formatted key/value pairs, several per line. In this case, I decided to put reflection to work for me, since all of the keys overlapped the set of names allowed in .NET object properties. On top of that, the tokenization can be done with String.Split(). I’m already on board. Here’s the guts of the parsing code:

while (true)

    string line = reader.ReadLine();

    if (line == null)

        break;

    string[] pieces = line.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);

    if (pieces.Length == 0)

        continue;

    string delimeter = pieces[0];

    switch (delimeter)

        case "StartCharMetrics":

            ParseCharMetrics(metrics, reader, GetInteger(pieces[1]));

            break;

        default:

            SetProperty(metrics, delimeter, pieces);

            break;

    if (line == null)

        break;

SetProperty is very simple – it just looks for a property named by delimeter with a setter and when it finds it type coerces the string value to the property type and sets it. Most of the conversion is done with System.Convert, which is easy.

For the main AFM file, I project the data onto an object that looks like this:

class GlobalFontMetrics

    public string FontName { get; set; }

    public string FullName { get; set; }

    public string FamilyName { get; set; }

    public string Weight { get; set; }

    public double[] FontBBox { get; set; }

    public string Version { get; set; }

    public string Notice { get; set; }

    public string EncodingScheme { get; set; }

    public int MappingScheme { get; set; }

    public int EscChar { get; set; }

    public string CharacterSet { get; set; }

    public int Characters { get; set; }

    public bool IsBaseFont { get; set; }

    public double[] VVector { get; set; }

    public bool IsFixedV { get; set; }

    public double CapHeight { get; set; }

    public double Ascender { get; set; }

    public double Descender { get; set; }

    public double StdHW { get; set; }

    public double StdVW { get; set; }

    public double XHeight { get; set; }

Now, all of this code is scaffolded into my unit tests and the output of each test is one or more .cs file containing code that constructs the tables from the AFM data. These source files are then added into the main project – but not automatically.

Now, suppose that you have source data that isn’t quite so easy to parse as AFM files. In my case I needed to build encoding tables for the various supported standard encodings in PDF, including StandardEncoding, MacRomanEncoding, and WinAnsiEncoding. These are listed out in the spec as tables. Fortunately, I could copy them within Acrobat and then paste them into Excel. From Excel, I ran a set of functions that transformed the data into abbreviated lists that I could use and then was able to turn that into C# with a handful of regular expressions. This is not as ideal as the tables are not as easily reproducible, but hopefully this won’t have to be done again.

All in all, the code and Excel chicanery took me two days to implement, verify, and unit test, far less than just typing in the tables and I’m far more confident that the data is correct.

Failure Modes

Tue, 19 Feb 2013 14:41:27 GMT

Software engineering is funny. It shares a lot with Computer Science (which honestly, should be called applied mathematics) and it shares some things with other engineering disciplines. With other engineering disciplines, it shares the need for clear processes for planning projects, managing work, ensuring quality, and handling defects. I say that it shares the need because not every shop actually does all of these things and there is certainly no one good standard for any of these. This is an industry problem.

One of the many nice things about being married to a real engineer is that I get to hear a lot about engineering and manufacturing process and one of the things I’ve heard her (and other engineers) talk about is FMEA: Failure Mode and Effects Analysis. This is process whereby a component can be analyzed for failure and severity or probability of failure can be reduced or eliminated. This is what I thought of when one of my LCD monitors failed.

We believe that engineers work better when there is more screen real estate available to them. We also believe that an investment in a good pair of monitors will pay off in terms of other resources saved. For example, our office supply sales representative asked us in all honesty if we were buying our paper from another source, since we go through very little paper (but a great deal of coffee). We purchased a fair number of these LCD monitors from a well-known consumer electronics manufacturer. In a few years, they started failing. In the past 6 months we have had 4 fail. Every single monitor failed in exactly the same way: the display went blank and the power light went off. After a brief pause, the monitor started back up again. The frequency of failures increase until the monitor fails to work at all. This to me screams of being a very analog problem, probably power related. To date, 68% of our monitors failed this way.

I contacted the manufacturer of these monitors to find out if there are replacement parts available, hoping that they would have an FMEA put together with this device that would pick out the likely culprit. I received worse than no help from the manufacturer, but Elaine will talk in more detail from a support point of view about what they did wrong and how they could’ve done it right.

Since I’m alone in this I chose to ignore the manufacturer's lawyers.

By the way – unlike this manufacturer, I’m going to say that if you’re deciding to do this, you should understand the risks. Power supplies in electronic devices can have components that will hold onto a charge long after they’ve been shut off. If you’re uncomfortable doing something like rewiring parts of your house, listen to your discomfort and don’t do this since the charge in a typical power supply cap can give you a nice burn or stop your heart. You know, bad things if you’re not appropriately careful.

I took the monitor apart and looked over the various boards to see if anything obvious was out of kilter and here’s what I found:

There are three of these capacitors on the board used to drive the CCFL that is used as a backlight to the LCD display. If you look at the top of the cap, you can see it bulging up. This is a sign that this part is failing or has failed. The manufacturer either used the cheapest caps they could find or used underrated parts or both (or heck, even something else). The point is that all three of the capacitors on this board look like this, and I would expect a large consumer electronics manufacturer to know about this, to admit to it, and to have a well-defined process for managing it, as well as to have fixed the problem in later revisions (and I can tell you that the manufacturing dates indicate on our devices that they likely did nothing of the sort).

Unfortunately, this part isn’t well-marked so I can’t tell you what the capacitance or the rating are, but taking a guess, this particular part probably cost them a few cents in quantity, whereas a higher quality part would have cost roughly 10 cents in quantity. So someone looked at the design and chose an off-brand manufacturer for the part in order to save 25 cents on the assembly.

The actual cost of this problem was probably far higher in terms of in-warrantee repairs. Sadly, the most costly loss to this manufacturer is in terms of customer loyalty. I had a CRT from the same manufacturer that I used for 10 years before replacing it with a smaller footprint, less power-hungry LCD. That CRT looked every bit as good on the last day as it did on the first day. The shoddy quality of these LCD devices and the especially poor customer service is such that I will never purchase another product from this manufacturer again and if I have a say in the matter, I will strongly discourage anyone I know or work for from purchasing their products.

By comparison, I have a workstation made by another well-known consumer electronics manufacturer on my desk which I use for my day-to-day work. The computer shut down without warning. We reported this to the manufacturer and even though it was out of warrantee, they sent us a replacement motherboard and power supply which arrived the very next day. When we replaced the board, we noted that the bad motherboard had several capacitors that were bulged up. The replacement motherboard had caps made by a different manufacturer.

And while a desktop workstation is a different beast than a monitor, the desktop manufacturer demonstrated that the proper way to handle this type of problem is with alacrity not with incompetence.

Tying Things Together: Why Typography Matters

Fri, 10 May 2013 11:26:31 GMT

Quick – take a look at this excerpt from a Dr. Seuss book:

I took this picture with my phone shortly after reading with my son and found this page particularly jarring. Like many technologies, automated type came from a hand-driven process. Writing used to be hand done until Gutenberg and then after, it’s been a continual struggle to get technology to be able to create something that can be done by a talented calligrapher. In this case, the problem is ligatures. Ligatures are sets of glyphs that are tied together (ligated) by their shapes. They are necessary because they improve the appearance and readability of a document. Here is a pretty good blog entry on ligatures.

Now look back at the Seuss. Here’s what I saw immediately (and I am not a typographer):

which are all pairs which should be replaced with an equivalent ligature. In particular, the fl is bad because of the f just barely touching the l and in the ffi, the dot from the i is almost but not quite hitting the second f. It feels off to me.

I first encountered ligatures while I was working on Adobe Acrobat version 1.0. I was assigned the task of “fixing” the built-in find tool, which as it stood could find a single word in the document and no more. I built it up to handle phrases and text that was perhaps on a curve (which made maps searchable). Working on this tool taught me about ligatures because, for example, that ffi in the document was represented by a single character which may or may not bear any relation to the actual glyph. So the text consuming code had to internally undo the text encoding and then undo the ligature expanding it to something that could be matched, but it had to keep the mapping so that we understood that three characters in the search key might not map to three glyphs on the page for highlighting. It was interesting and as a result my eye has been trained to spot ligatures, or more precisely to spot when ligatures are not there.

Here is what the above text looks like with ligatures in place – I approximated the font. It’s not quite right, but it’s close enough so you can see the difference

And to its credit, Photoshop did the ligatures for me as I typed in the text. I’m glad that another engineer has had an eye for this detail. I can’t wait for this to be better supported on the web. Chrome, Firefox and Safari appear to have support for it on Windows, but not Internet Explorer.

How to Split a Cubic Bézier Curve

Fri, 24 May 2013 11:47:08 GMT

Today I’m going to get all mathy on you. Don’t worry about it – it’s going to be pretty simple math and in the end we’re going to learn how to split a cubic Bézier curve into two new curves.

First, let’s start off with parametric equations. This is a type of equation that adds a new variable, t, which can be thought of as time. In our world, t is going to range from 0 (the start) to 1.0 (the end). So for example, if I have a line segment from point A to point B, then point A is at time 0, point B is at time 1 and the midpoint is at time 0.5.

Let’s look at midpoint briefly – you probably learned midpoint as this:

x’ = (x₁ + x₀)/2

y’ = (y₁ + y₀)/2

or simply, the average of the x’s and the y’s. But let’s have some fun with this. I’m going to only work with x components, but I assure you that this works just fine with both. First, I’m going to rewrite that divide by 2 as a multiply by 0.5:

x’ = (x₁ + x₀) * 0.5

Now, let’s distribute this over the terms:

x’ = 0.5x₁ + 0.5x₀

Now, I’m going to rewrite the second term as an equivalent:

x’ = 0.5x₁ + -0.5x₀ + x₀

We simplify and associate:

x’ = (x₁ – x₀) * 0.5 + x₀

This is an equivalent, if slightly more general version of midpoint. So why did we do that? Because we can now replace that 0.5 with t as time and we have a complete parametric equation for a line:

x’ = (x₁ – x₀) * t + x₀

y’ = (x₁ – y₀) * t + y₀

I’ve also given you the formula for linear interpolation from one point to another – it’s the same. And to help you along, I’m going to give you a new verb, lerp, which means to linear interpolate from A to B.

Now, onto cubic Bézier curves. Here is a simple cubic Bézier curve which is defined by 4 points – two end points and two control points

P0 and P3 are end points and P1 and P2 are the control points. The parametric formula for this curve is this:

x = a_xt³ + b_xt² + c_xt + x₀

y = a_yt³ + b_yt² + c_yt + y₀

It looks like a handful, but it’s not really that bad – it’s a third degree polynomial that is a function of t and not of x or y. One tricky part is understanding the relationship between the four control points and the coefficients of the t terms. Again, let’s work with just the x side, since the y equation will work out the same. I’m not going to derive these for you – trust me.

a_x = x3 – ( 3 * x2) + (3 * x1) – x0

b_x = (3 * x2) – (6 * x1) + (3 * x0)

c_x = (3 * x1) – (3 * x0);

The variables x0 through x3 correspond to the X coordinates for points P0 through P3 in the diagram above. So let’s look at splitting this Bézier in half. We’ll do this graphically by first drawing in some guides:

I’ve added a line between P1 and P2 and added three new points, P4, P5, and P6. Each of these points are at the midpoint of the segment on which they lie. Now, let's connect the midpoints together:

Here I’ve added two new midpoints, P7 and P8. Repeat again to leave us with a new line and midpoint:

And P9 is on the right on the curve. Furthermore, the first section of the split curve from P0 to P9 can be described with the four points, P0, P4, P7 and P9:

and the second part of the split curve and be described with points P9, P8, P6 and P3:

If you’re still with me, you’ll note that if you keep splitting the subcurves, you will eventually draw every point on the original curve. And you can do this all with calling midpoint successively. Generally speaking, in software we like this because midpoint is one add and one divide by two. If you’re working in fixed point, this is wonderful because that becomes an add and a bitshift, both very fast instructions. In theory, I could do the subdivision of a curve in 14 instructions (plus about 7 instructions of overhead) per coordinate. That’s really not a lot. There’s a problem though – splitting a Bezier this way to, say, draw it with a series of straight lines is not so good as it’s not obvious when you should subdivide further or be satisfied with what you have. In other words, a small change in t may make a substantial change in the distance traveled along the curve and the next change in t is likely NOT going to end up with the same change on the curve. So midpoint is not really the best way to do this. What if we wanted to use any arbitrary t? We could use the general formula above, but that may not be the best choice – we don’t like the cubes and squares so much and while that will give as a point on the curve, it won’t let us actually split the curve because we would be missing the new control points.

So let’s go back to our original midpoint formula and throw it away. Instead of using midpoint, we’re going to use the parametric equivalent. So give the T you want, you get P4 by lerping from P0 to P1, you get P5 by lerping from P1 to P2, you get P6 by lerping from P2 to P3. Moving to the next step (red), you get P7 by lerping from P4 to P5, you get P8 by lerping from P5 to P6. Finally, to get P9 by lerping from P7 to P8. In implementation, each lerp is a multiply and two adds. 6 lerps is therefore 6 multiplies and 12 adds, or about 30 instructions.

Now if we used the polynomial form each coordinate would be 5 multiplies and 3 adds per coordinate, but we wouldn’t have the control points of the new curves and getting them turns out to be more work than just doing all the lerping in the other solution.

There are two closely related problems that fall out from this work –

1. How do I draw a cubic Bézier with the fewest/optimal straight line segments?
2. What is the length of a cubic Bézier curve?

If you can solve the first problem, you can come up with an approximation for the second. We’ll save this for another time, though.