Geometer»Blog
Andrew Reece
Apologies for the long delay since my previous post - I quit my job, and I've been focusing more on things that will pay the bills...

I'm starting to think about UI a bit more, for which colour is often very important. Something that's fairly easy to do, but often overlooked, is to make sure that colour choices are suitable for colourblind users as well as people with normal colour vision (if that's even done at all). Since about 8% of people are colourblind, it's a significant chunk of your user base to alienate if you get it badly wrong.

I've put together some utilities for evaluating colours and simulating colourblindness for each missing cone. This is as a C header library and some glsl matrices.

Check it out on Github.
Andrew Reece
Say goodbye to jaggies, it's smooth sailing (and rasterization) from here on out!

I finally got round to getting my rendering to work on OpenGL.
This lets me do things like animation smears really easily.

I'm not sure what the compatibility is like for graphics cards, but if it doesn't work you can hit F6 to toggle software rendering.

Download from the Github repo

Andrew Reece
I don't think I'm doing anything revolutionary with my undo system, but hopefully making the reasoning behind it very explicit will elucidate any missing steps in the reader's or my thinking.

A large part of this is trying to define 'units of interaction' for the user and then matching that to what can be robustly determined and stored in the software.

I describe this here as a roughly linear sequence for the sake of clarity. In reality the process was more iterative, and broadly follows Casey Muratori's Semantic Compression approach.

Throughout the article, I use 'units of interaction', 'units of action', 'task units' etc interchangeably.


Contents
  • Contents
  • Intro
  • Naive undo states
    • Why this is not good enough
  • Actions
  • User Actions
    • Theory
      • Action Cycle and Principles
      • Error types
      • Action hierarchy
    • Example action set
    • User-centred goals
      • Functionality goal - cost saving
      • Consistency
      • Mapping
    • Error prevention
  • Technical considerations
    • Objectives
    • Triggers and choice of representation level
  • Representation
    • Undo
    • Redo
    • Collection data structure
    • Resultant structs
    • Mismatch between user actions and software actions
    • Function Layout
      • Action Functions
      • Undo/Redo functions
    • Required restructuring
  • Future possibilities for actions
  • Conclusion
  • Further reading

Intro

If you've used any editing software, for text, images or something else, you've almost certainly had to use the undo function. Its purpose is fairly clear. Simply put, people commit errors all the time, and so it's necessary to have a way to fix them.

On top of this, having a robust undo system allows users to have enough confidence in your software to rapidly experiment, safe in the knowledge that they can just undo if it turns out wrong.


Naive undo states

My first approach was to have a fixed array containing snapshots of the entire state at successive points in time. Once the array was full, the new states would wrap to the beginning. Each state had a separate memory arena assigned. Undos and redos would just change the index of state looked at, and base all of the interactions, rendering etc on that.

The state would be saved at various points in the interaction processing that seemed appropriate. Because the entire state was saved this could be a bit sloppy, because all the information required was in that one state.


Why this is not good enough

The naive approach wasn't going to work long-term, in large part because I wanted to have the option of indefinitely long undo history. It was doomed for replacement because it:
  • grows exponentially - this is the main reason. Every change also stores all the previous changes.
  • is awkward to access in code (State->Draw[State->iCurrentUndoLevel].Points[State->iActivePoint]),
    which would be further complicated by the addition of layers.
  • is more difficult to implement than the improvements described later:
    • partly due to lessons learnt by doing this first.
    • it has general fiddly bits in terms of:
      • keeping track of the start and end of the circular buffer.
      • special-casing before the array was full.
      • memory management - making sure that the next state was large enough to contain any changes from the current state.

Actions

The change in thinking was that rather than storing absolute states, I should store the difference between them. The things that cause the change in state are the actions by the user. Broadly speaking, each time the user does an action, I should record what it is, then be able to undo/redo it at will.

But what counts as a user action?


User Actions

Theory

It's worth taking a slight detour into UX/ergonomics, as we're stepping into their wheelhouse. Not all of this is applied directly in this article, but I think that it provides background/context and informs intuitions in a useful way.

That said, it's not necessary to understand the rest of the article, so feel free to skip it if you want a shorter read.


Action Cycle and Principles

Don Norman's 7 step model of action/action cycle provides a breakdown of interaction from the user's perspective, which allows us to better target corrections.

Goal formation stage
  1. Goal formation.
Execution stage
  1. Translation of goals into a set of unordered tasks required to achieve goals.
  2. Sequencing the tasks to create the action sequence.
  3. Executing the action sequence.
Evaluation stage
  1. Perceiving the results after having executed the action sequence.
  2. Interpreting the actual outcomes based on the expected outcomes.
  3. Comparing what happened with what the user wished to happen.
These lead to 4 principles of good (UI) design: 1. Visible system state 2. Consistent conceptual model 3. 'Intuitive' mappings between action and consequence 4. Continuous feedback of past and potential actions

-- Don Norman (Action Cycle - Wikipedia)


Error types

Undoing is typically for the purpose of correcting (potential) errors. I won't go too far into this, but it's useful to have some vocabulary and context for thinking about errors. Different error types may require different prevention and recovery methods
  • Mistakes - conscious decision to do something that turns out to be wrong i.e. forming the wrong goal.
  • Slips - unconscious automatic behaviour resulting in unintended consequences.
    • Capture error - a common script overriding the intended action (e.g. driving to work instead of to the shops).
    • Description error - do the right thing with the wrong object.
    • Data-driven error - information from the world intruding into an action.
    • Associative activation error - Freudian slips (roughly).
    • Loss-of-activation error - forgetting.
    • Mode error - do the otherwise right thing in a mode that interprets it differently.
Errors can also be categorised as:
  • Commission - did something incorrectly.
  • Omission - didn't do something that should have been done.
[Don Norman (Design of Everyday Things)]


Action hierarchy

A common start point for human factors/ergonomics analysis is a Hierarchical Task Analysis. This involves recursively breaking down the component tasks required to achieve a larger task/goal based on observations of people performing the task. The end result is similar to a hierarchically-organized graph of functions that call a number of other functions, which each call a number of other functions... The main takeaway is that there are multiple possible levels of detail that could be appropriate to consider 'an action', as you'll see in the upcoming example.


Example action set

It's often easiest to design a user interface if you can reference a concrete example of something a user might do. This is the UI/UX equivalent of

Casey Muratori

Always write the usage code first (broadly talking about API design).

I'll be running with this example for the rest of the article. It's not comprehensive, but other actions follow a similar line of reasoning. As already mentioned, tasks can be broken down in granularity into a hierarchy. Here's a slice of an example goal/task hierarchy for a drawing in Geometer:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
0.  Draw a cathedral in profile view                 /* Entire drawing */
    ...
    4.  Draw the east wing                           /* Section of drawing */
        ...
        4.6.  Draw an arch                           /* Architectural component */
            4.6.1.  Draw the left-hand arc           /* Discrete shape */
                4.6.1.1.  Add a focus point          /* Shape component */
                    4.6.1.1.1.  Move the cursor to the bottom-right point  /* Direct input */
                        4.6.1.1.1.1.  Grip mouse     /* Joint movement */
                        4.6.1.1.1.2.  Retract shoulder girdle
                        4.6.1.1.1.3.  Extend, laterally rotate and adduct shoulder
                        4.6.1.1.1.4.  Allow passive elbow flexion
                        4.6.1.1.1.5.  Ulnar deviate wrist

                    4.6.1.1.2.  Check that the intended point is snapped to
                    4.6.1.1.3.  Click and release the left mouse button at that point

                4.6.1.2.  Start the arc
                    4.6.1.2.1.  Move the cursor to the bottom-left point
                    4.6.1.2.2.  Check that the intended point is snapped to
                    4.6.1.2.3.  Click and hold the left mouse button at that point

                4.6.1.3.  Finish the arc
                    4.6.1.3.1.  Move the cursor to the top-centre point
                    4.6.1.3.2.  Check that the intended point is snapped to
                    4.6.1.3.3.  Release the left mouse button at that point

            4.6.2.  Draw the right-hand arc
                ...

Note that:
  • If asked "what are you doing?", you could accurately answer at any level;
    there are multiple viable levels of analysis - you can be as detailed or abstract as you like.
  • The action cycle occurs at each level from direct input up
  • Errors could occur at any level
In magical UI land, the unit of interaction should be at whatever level in the hierarchy the user thinks it is at the time. I'm not sure to what extent you can implement variable hierarchical levels of undo, let alone communicate it in a way that makes sense to the user. As such, we'll start with a single level-of-detail action unit that is good enough for most purposes. This may be extensible to get closer to magical UI land, as hinted at in Future possibilities for actions.

It's also worth noting that other interface features and external programs can fill the role of dealing with high-level units of interaction, particularly saves, backups and version control.


User-centred goals

As already mentioned, the primary purpose of undo is to correct mistakes. This is not the only purpose, however - it's also useful for: - reminding users of the sequence of actions they've just taken as a prompt for what is needed next. - repeatedly returning to a common point after temporarily exploring multiple elaborations from it.

There are a few axes on which to evaluate an undo/redo system.
  • Functionality goal - cost-saving
  • Consistency goals:
    • Self-consistency
    • Consistency with other programs (less important, but better if possible)
  • Mapping

Functionality goal - cost saving

An action should represent some notable cost to the user: in precision or time or effort.

If it's just as easy to actually redo the action as to use the redo input, there's not that much point in having the control. Too small action sizes are similarly irritating for undo as well: consider a text editor that removes one letter per undo. With this in mind, we'd like to define task units higher up the hierarchy to save as much effort as possible per undo/redo. We don't, however, want them to be too high up, otherwise we'll unavoidably skip back past too many valid actions, which will then require manual redoing.

One way to think about this is, "if the user realises they made an error here, how many times will they have to undo, and how much will they have to manually redo in order to return to the state immediately before the error".

The aim here is to minimize estimated total effort in error recovery

An empirical question that would be useful to know the answer to is "At what level do most errors occur?". Without an answer, it seems better to lean too fine-grained than too coarse-grained - it's much harder to increase resolution than decrease it.


Consistency

Self-consistency:
  • Undo and redo should have the same unit of action.
  • Units of action should be the same size.
External consistency: - I'll be using Ctrl+Z for undo, Ctrl+Y/Ctrl+Sh+Z for redo, as with other programs. - Units of interaction will represent a similar time investment.
  • The user should know in advance what will disappear when they undo.
    • This minimizes time spent in the evaluation stage of the action cycle.
    • Actions should be demarcated in some way, e.g. with distinct start and end points.

Mapping

Quality of mapping can be evaluated of in terms of how well the application matches what the user expects from the first time they undo. Consistency plays a large part of expectations in future interactions How well does it fit their initial mental model?

In order to make a clear mapping, actions should correspond fairly directly to a pattern of inputs rather than some downstream changes.


Error prevention

I won't go into this too much here as it's not really in the intended scope of this article, but helping to minimise stupid errors is important. Errors from bad design:
  • waste your user's time
  • make the user frustrated with themself and your product
  • undeservedly diminish the user's sense of competence/mastery
  • reduce the chance of continued use of your product
Note the qualifier 'from bad design'. Some increased likelihood of error occurs as a side-effect of flexibility and other positive qualities.

Mode errors are among the most insidious. Vim is a classic example for this: users try to type but the editor seems to go haywire because it is not in 'input' mode. It is not immediately apparent which mode vanilla Vim is in, which worsens the problem.

I try to avoid this in Geometer by making changes in mode obvious, discrete and brief. I still have more work to do to improve this.


Technical considerations

I have not yet talked about computer actions or representation. Without a good idea of what we're aiming for, it's easy to prematurely limit the technical representation to the first/easiest thing we think of. We should be aware of technical limitations, but we want a user-focused goal to shoot for, even if we fall short.


Objectives

Nothing novel here, but some things to keep in mind:
  • Quick to read/write
  • Not memory intensive
  • Deterministic in terms of:
    • Interpreting a pattern of input as 'an action'
    • Recreating that action
  • Able to traverse forwards and backwards
  • Changes are self- and externally-consistent, e.g.
    • Multiple undos followed by an equal number of redos returns to the same place
    • A redo makes the same state changes that doing the action manually would (excluding any changes to the action array)

Triggers and choice of representation level

Working up from the lowest level (which incidentally tends to be how humans search for the cause of errors), let's consider how well the task levels fit the objective of determinism:
  • Joint movement - no way to directly interpret
  • Direct input - difficult to tell how much movement to classify as an action; state doesn't necessarily change
  • Shape component - needed to reconstruct shapes, a single function is executed for each
  • Discrete shape - this is demarcated by leaving the normal state, going through the drawing process, then returning to the normal state again
    (see the explanation of state-based input-handling in my 1 year-in article).
  • Architectural component - this is drawing-specific, and without additional user tagging would need some fancy heuristics.
    This (and higher levels in the hierarchy) are thus ruled out as non-deterministic.
So we're left with shape components and discrete shapes as viable levels for units of interaction. The shape components need to be stored, but the input demarcation of discrete shapes seems more appropriate for a user's mental model. Additionally, returning to part-way through a shape would leave the program in a non-normal state, encouraging mode errors.

For Geometer, shape components have the useful property of being the same as other discrete-shape-level actions: adding points. That is to say that shape components are a subset of the discrete shapes. 'Hierarchy levels' is a leaky abstraction! This allows me to somewhat cheat here: I can store both.

This should allow for something that broadly matches user-based objectives.

Now we have an idea of what level we want to capture, how best to represent this?


Representation

The action representation must provide sufficient information for traversal in either direction.


Undo

Some changes are directly invertible, i.e. the way to reverse can be found from how they work normally. A change of basis, for instance, is primarily a matrix multiplication. This can be reversed by multiplying by the inverse matrix. Other changes need additional information: points only need a position to be added, but its index in the Points array is needed to reverse this. The inverse is true for deleted points.


Redo

This mirrors adding/removing shapes, and is perhaps even easier. This should just do the same thing that the user did, so the initial handling and the redoing can be collapsed into one function.

Not all actions have the same 'remove' equivalent, so Remove___ actions are treated as separate entities rather than inversions of the original action (in the enum).


Collection data structure

I like arrays:
  • They're easy to write bug-minimal code for (particularly with a foreach construct).
  • They are fast to traverse:
    • They're cache-friendly (all the data is in contiguous memory).
    • You often get an efficiency/speed bonus from cache prefetching.
  • Elements at arbitrary indices can be accessed in O(1) time.
  • Bounds checking can be added and toggled pretty easily.
  • They're already serialized for saving to disk.
Unless there's a good reason otherwise (see Future possibilities for actions) I will stick with them.

The data access pattern here is normally going to be linearly progressing either forwards or backwards with the occasional random access, which is a good fit for arrays.

They'll need to be resized as more and more actions are added, so it'll have to be a dynamic array (allocated and reallocated on the heap) rather than simple fixed-size static arrays. See Sean Barrett's stretchy buffer code and Per Vognsen explanation of dynamic arrays as part of Bitwise.


Resultant structs

The data needed for different actions are of comparable size, but not all exactly the same in contents. This is a textbook case for using discriminated unions. That is, indicating the kind of action with an enum/integer ID, then interpreting the following data based on that kind.

My current representation of shapes is as a union, but it needn't necessarily continue like that. As a result I have to discriminate between shape types at the action level. It would be redundant to also have the shape Kind stored in both the shape and the action. I have to have the action Kind, so I only include the union for shapes.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
typedef enum action_types {
    ACTION_Reset   = 0,
    ACTION_Line    = SHAPE_Line,    /* 1 */
    ACTION_Ray     = SHAPE_Ray,     /* 2 */
    ACTION_Segment = SHAPE_Segment, /* 3 */
    ACTION_Circle  = SHAPE_Circle,  /* 4 */
    ACTION_Arc     = SHAPE_Arc,     /* 5 */
    ACTION_Point,
    ACTION_RemovePt,
    ACTION_RemoveShape, /* This will probably turn out to be insufficient */
    ACTION_Basis,
    ACTION_Move,

    ACTION_Count,
    ACTION_SHAPE_START = ACTION_Line,
    ACTION_SHAPE_END   = ACTION_Arc
} action_types;

typedef struct action_v2 {
    i32 Kind;   /* 4 bytes  */
    union {     /* 20 bytes */
        struct reset_action {
            u32 iAction;    /* where I'm resetting back to */
            u32 cPoints;    /* maybe needed for future stuff */
            u32 cShapes;    /* maybe needed for future stuff */
            f32 Empty_Space_To_Fill_1;
            f32 Empty_Space_To_Fill_2;
        } Reset;

        struct shape_action {
            u32 iShape;
            u32 iLayer;
            shape_union;    /* Contains point indices for line/circle/arc */
        } Shape;

        /* struct move_action Move; - temporarily retired while I figure some stuff out */

        struct pt_action {
            u32 iPoint;
            u32 iLayer;
            v2 po;
            u32 Empty_Space_To_Fill;
        } Point;

        basis_v2 Basis;
    };
} action_v2;

Mismatch between user actions and software actions

Given what I've said so far, an example of a user action could be adding an arc. The process of drawing the arc also adds up to 3 new points (if they weren't there already): the focus, the start of the arc and the end of the arc. These need to be added as actions so that the software knows what to undo/redo, but as I've already said, the user action is adding an arc - I don't want the user to have to undo 4 times (3 points + 1 shape) for 1 conceptual action.

My solution to this is pretty simple: I negate the Kind value for all but the last action. The last action is thus conceptually the 'user action' and I have to make sure the actions are ordered accordingly.

I end up with shape components as the software actions and discrete shapes as user actions.

There's an additional wrinkle that the components may already exist. Ways to deal with this are:
  • Not add them (my current strategy) - saves memory and processing, but may make some things harder.
  • Add them and notate them in some way (e.g. high bit in enum)
  • Add them without notation, leave ignoring them to my idempotent AddPoint function, which

Function Layout


Action Functions

As alluded to earlier, more rigour is required for action/delta-based rather than state-based undos because you need to be careful that all the necessary changes are captured. I do this by attaching the action-adding code to the code that makes the relevant change.

Each software action has 2 related functions:
  1. Making whatever changes are necessary without pushing a new action.
    This is used in the undo/redo code, to avoid corruptions of the action array.
  2. A wrapper function that calls (1) then adds an action if necessary.
    This is used in the normal input/interaction handling code.
Below is the basic structure of this for shapes:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// returns true if shape is new (i.e. action to be added)
b32 AddShapeNoAction(state *State, shape Shape, uint *iShapeOut) {
    Assert(ShapeIsValid(Shape));
    b32 ExistingShape = 0;
    uint iShape;

    // check if shape exists already
    for(iShape = 1; iShape <= State->iLastShape; ++iShape) {
        if(ShapeEq(Shape, State->Shapes[iShape])) {
            ExistingShape = 1;
            break;
        }
    }

    // add new shape if needed
    if(! ExistingShape) {
        Push(&State->maShapes, Shape);
        iShape = ++State->iLastShape;
        AddAllShapeIntersects(State, iShape);
    }

    *iShapeOut = iShape;
    return ! ExistingShape;
}

// returns position in Shapes array
uint AddShape(state *State, shape Shape) {
    uint iShape = 0;
    if(AddShapeNoAction(State, Shape, &iShape)) {
        action Action = ActionShape(iShape, Shape);
        AddAction(State, Action);
    }
    return iShape;
}

Non-user actions come before the user action. Here's how I make sure that happens for adding a line segment:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// returns position in Shapes array
inline uint AddSegment(state *State, uint P1, uint P2) {
    shape Shape;
    Shape.Kind = SHAPE_Segment;
    Shape.Line.P1 = P1;
    Shape.Line.P2 = P2;
    return AddShape(State, Shape);
}

inline uint AddSegmentAtPoints(state *State, v2 P1, v2 P2) {
    uint iP1 = AddPoint(State, P1, -ACTION_Point);   /* these will add new actions if the points are new */
    uint iP2 = AddPoint(State, P2, -ACTION_Point);   /* negative -> non-user action */
    return AddSegment(State, iP1, iP2);
}


Undo/Redo functions

The undo/redo functions are divided into a function for software actions and a loop repeats these until a user action is reached.

The simple form of undo/redo works at the component level by switching on the type, then doing the action/its reverse as needed. Here's an abridged version:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void SimpleUndo(state *State) {
    action Action = State->Actions[State->iCurrentAction];
    switch(AbsInt(Action.Kind)) {    /* whether or not it is user-level is dealt with elsewhere */
        /* ... */

        case ACTION_RemoveShape:
        {
            shape *Shape = ShapeFromAction(State, Action);
            uint iShape  = 0;
            AddShapeNoAction(State, Shape, &iShape);
        } break;

        case ACTION_Segment:
        case ACTION_Circle:
        case ACTION_Arc:
        {
            RemoveShape(State, Action);
        } break;

        /* ... */

        default: { Assert(!"Unknown/invalid action type"); }
    }

    --State->iCurrentAction;
}


void SimpleRedo(state *State) {
    action Action = State->Actions[++State->iCurrentAction];
    int UserActionKind = AbsInt(Action.Kind);
    switch(UserActionKind) {
        /* ... */

        case ACTION_RemoveShape:
        {
            RemoveShape(State, Action);
        } break;

        case ACTION_Segment:
        case ACTION_Circle:
        case ACTION_Arc:
        {
            shape *Shape = ShapeFromAction(State, Action);
            uint iShape  = 0;
            AddShapeNoAction(State, Shape, &iShape);
        } break;

        /* ... */
    }
}

The user-level undo/redo then works as follows:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
b32 Ctrl_Z = Keyboard.Ctrl.EndedDown && Press(Keyboard.Z);
b32 Ctrl_Y = Keyboard.Ctrl.EndedDown && Press(Keyboard.Y);
b32 ShiftHeld = Keyboard.Shift.EndedDown;

if(Ctrl_Z && ! ShiftHeld &&
   State->iCurrentAction > 0)
{ // UNDO
    do { SimpleUndo(State); }
    while( ! IsUserAction(State->Actions[State->iCurrentAction]));
}

if((Ctrl_Y || Ctrl_Z && ShiftHeld) &&
    State->iCurrentAction < State->iLastAction)
{ // REDO
    do { SimpleRedo(State); }
    while( ! IsUserAction(State->Actions[State->iCurrentAction]));
}


Required restructuring

I didn't initially distinguish between user-added points and intersections. Adding intersections into the action array would have added a lot of confusion once deleting shapes was working. There would be a non-deterministic number of unnecessary additions for every shape added.

Intersections now only become user points once they have been drawn with. They are calculated based on shape positions and stored in their own dynamic array. After an undo/redo that involves a shape, they are recalculated.


Future possibilities for actions
  • One of the things I like about the action paradigm closely following the user-input model is that it seems like it would lend itself well to macro/function creation.
  • The changes at this level can be fairly easily visualised in a history thumbnail.
  • Although unwise to do automatically, the user might find it helpful to manually group actions together into what would become a hierarchy.
  • Actions could be laid out as a tree, so rather than new actions after undos overwriting all potential redos, they're just written on an new branch.
  • Have variable-sized action data structures. This would save a small amount of memory but would be more error-prone and could make some operations slower.

Conclusion

In this article we:
  • Looked at human factors theory for backing in terms of action cycles and error types.
  • Considered the factors that would make a unit of interaction appropriate for users.
  • Determined some technical objectives for an action representation.
  • Came up with a high-level description of what would fit technical and user objectives.
  • Determined appropriate data structures for actions.
  • Ensured that actions would be captured at the right times.
  • Created a simple and user-level undo/redo.
  • Speculated on potential future developments.
I think this is quite thorough from a theoretical perspective, but would ideally have had some more end-user involvement. Based on use by me and my single test-user (my girlfriend), and given the similarity of my solution to other undo systems, I'm happy with the results so far.

Writing this has helped me clarify some of my own thoughts on the topic and simplify some of the code. Hopefully this has provided you some food for thought in terms of undo systems and interaction design more generally.

Please let me know if any sections were particularly helpful, or if they need any clarification.


Further reading

N.B. I get a kickback if you buy directly through one of these links (on Amazon UK). If you'd rather not do that for whatever reason, they're easy to find online.
  • 'Design of Everyday Things' - Don Norman (Amazon US, UK). This article was heavily influenced by the ideas in this book. I highly recommend it for anyone making anything that people will interact with (yes, that's intentionally broad!).
  • 'Human Error' - James Reason (Amazon US, UK). A classic work for a deeper dive on error than DOET.
Andrew Reece
At some point you'll probably want to include some data or resources into the executable itself (e.g. fonts, images etc). This is particularly true for my case, as I'm trying to keep to a portable single-executable model. That means that I can't keep resources in a surrounding folder and load at runtime, and I don't want to assume that the user already happens to have the files on their system.

Icons are one example of a useful resource that takes an application from looking amateurish to looking like a Real Product (tm).

This post will show some cross-platform methods of adding resources to your application, and a Windows-only method, with icons as an example.


Contents
  • Intro
  • Compiled resources (platform-independent)
    • xxd
    • GIMP
  • Linking (Windows-specific)
    • Linking icons as resources
      • RC file text
      • RC to RES
      • Linking the RES to your executable
      • Resource access from code
      • Using icons
  • Concluding thoughts

Intro

You can divide methods of including resources in your application into 3 groups based on when they are attached, each with an analogous form for adding libraries:
  • Runtime [.dll/.so files] - loaded with fopen and that family of functions.
    I won't be going into this here as there are tutorials for them all over the internet and it's not relevant to my use case.
  • Linked [.lib/.a files] - processed and added by the linker, these have to be 'found' in the executable at runtime.
  • Compiled [files added with #include] - added to source code, commonly as an array of bytes in a header.
Inherent in linking resources to your executable is that it will get larger. The resources that I'm using in an editor are few and small, and as such, the pros of portability and simplicity win out. If you're making a game with large textures and audio files, the trade-off may not be so appealing.

The ease of modding resources in a folder layout is also something that might be more appreciated for a game.


Compiled resources (platform-independent)

Adding resources via an array in a header file is the simplest in terms of runtime use: they can be accessed like any normal variable/array. As such, this is my preferred method unless there are major reasons to go a different way.


xxd

xxd is a command-line utility for interacting with binary files, primarily converting to and from hex data. It's normally a unix application, but it also comes bundled with the Windows version of Vim, which is handy for me... (You can access it directly through Vim with :!xxd ... or find it in the application's folder.)

The default output of xxd is what you see in a hex viewer, and is actually what I was using in my last blog post to validate my file format:
1
xxd test.geo



Hey, this is just a bunch of hexadecimal numbers; you can format numbers like this in normal C code by slapping "0x" at the front:
1
char Fifteen = 0x0F;

Why not just make an array of these and add them to the code?

Helpfully for our purposes, xxd has an option to format its output for an include file:
1
xxd -i test.geo test_geo.h

My test.geo file has changed since the hex dump image above, but here's a look at the current version.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* test_geo.h */
unsigned char test_geo[] = {
    0x47, 0x65, 0x6f, 0x6d, 0x65, 0x74, 0x65, 0x72, 0x01, 0x00, 0x06, 0x00,
    0x49, 0xd9, 0x86, 0x56, 0x8b, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0xce, 0xcc, 0xec, 0xc0,
    0x04, 0x00, 0x00, 0xc0, 0x66, 0x35, 0xec, 0x40, 0xbb, 0x6d, 0x6e, 0xc1,
    0xdc, 0x4c, 0xc0, 0xc1, 0xe2, 0x62, 0x46, 0xc1, 0x01, 0x00, 0x00, 0x00,
    0x03, 0x00, 0x00, 0x00, 0x09, 0x21, 0x21, 0x02, 0x00, 0x00, 0x00, 0x01,
    0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x02,
    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x09,
    0x00, 0x00, 0x00, 0xfa, 0xff, 0xff, 0xff, 0x01, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0xcd, 0xcc, 0x80, 0xc1, 0xcd, 0xcc, 0x4c, 0x3e, 0xfa,
    0xff, 0xff, 0xff, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x22, 0x84, 0xbf, 0xb4, 0x39, 0x4f, 0xc1, 0xfa, 0xff, 0xff, 0xff, 0x03,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf0, 0xb3, 0x3c, 0x40, 0xdb,
    0x74, 0xc9, 0x40, 0x05, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01,
    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x0a,
    0x00, 0x00, 0x00, 0xc0, 0xcc, 0xcc, 0x3e, 0x67, 0x66, 0x06, 0x41, 0x01,
    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0xcd,
    0xcc, 0x04, 0x41, 0x01, 0x00, 0x28, 0xc1, 0x01, 0x00, 0x00, 0x00, 0x02,
    0x00, 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xcd, 0xcc, 0xbd, 0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x0a,
    0x00, 0x00, 0x00, 0x34, 0x33, 0xaf, 0xc1, 0x66, 0x66, 0xf6, 0xc0, 0x03,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0x9a,
    0x99, 0x31, 0xc1, 0x34, 0x33, 0x63, 0xc1, 0x03, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 0x00, 0x1a, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0xa0, 0x41, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x01,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0x3f, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xcd, 0xcc, 0xcc, 0x3d
};
unsigned int test_geo_len = 419;

An array and a count of bytes - what more could you ask for!

Note that the size on disc of your h file will be about 6 times larger than the file you're including - you're using 6 bytes to encode a single one: "0x47, ". I tend to search and replace to remove the spaces, making it about 5x the orginal filesize. This shouldn't be a problem unless you're really strapped for space on your development machine. It won't affect the executable size.

I currently do this with a font. In one of my earlier releases I forgot that I was loading the font from disc at runtime, so the first feedback I got was that it was crashing on opening... not great!

You can also do some compression to save space in the executable. You then just need a way to decompress at runtime.

If you change the data contents of your files frequently, they can be converted to C headers as part of your build process (before you compile).

If you don't want to get xxd for whatever reason, there are alternatives out there, or you can make your own, which you can do pretty quickly.


GIMP

(Examples are from GIMP 2.8)

While xxd outputs generic bytes from any old file type, if you want to easily include some images, GIMP has a nice feature where it will let you export C source code/headers in RGB(A). This is the basic format:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
static const struct {
    unsigned int  width;
    unsigned int  height;
    unsigned int  bytes_per_pixel; /* 2:RGB16, 3:RGB, 4:RGBA */ 
    unsigned char pixel_data[700 * 400 * 4 + 1];
} gimp_image = {
    700, 400, 4,
    "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
    "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
    /* ... */
};

(Note the more compact string-based encoding.)



There are quite a few options, including basic run-length encoding, which dramatically decreases the size of images with blocks of colour. This also includes a macro for reading the RLE data.

You can trade off a significant reduction in executable size with a slightly easier file to read. Have a play around with the various settings and see what you get.


Linking (Windows-specific)

The other option we're exploring here is for the linker to bundle the file into the executable. Once it's there, we need a way to find it at runtime. On Windows, this is done using the 'Resource' API/system. The simplified process for this is:
  1. Notate the files you want included in a .rc text file
  2. 'Compile' the .rc file to a .res file
  3. Link the .res file in with your program
  4. Access the resource data in your code
  5. Use the data
I'll work through this with icons as an example. It seems as though you have to include icons with this method to get them to show up everywhere you want.


Linking icons as resources

I'll assume here that you have an icon. If not, you can create and export .ico files with GIMP.


RC file text

These have a pretty simple format: the name of the resource (as you'll access it in the code), the type, and the relative file location.
1
2
Icon       ICON "G_32.ico"
IconSmall  ICON "G_16.ico"

There are a number of types, including a generic/custom data format.


RC to RES

This just involves running the rc executable on the RC file. (The nologo flag just stops it from spitting out copyright information).
1
rc -nologo geometer.rc

This outputs geometer.res. If you're doing this from the command line then as with cl, you have to run the vcvarsall.bat in the shell before you run rc:
1
call "C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\vcvarsall.bat" x64


Linking the RES to your executable

This is just linked as you would a static library:
1
cl ...flags... win32_geometer.c /link ...libs... geometer.res


Resource access from code

Typical resources are accessed with FindResource and LoadResource. Some of these can be accessed more succinctly, e.g. LoadCursor and LoadIcon.


Using icons

Just having the icon resource attached adds the icon to the executable and associated files in Windows Explorer/My Computer.



Adding the icons to the top-left of the program window and the taskbar is easy if you're loading the window class yourself:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
WNDCLASSEX WindowClass    = {0};
WindowClass.cbSize        = sizeof(WNDCLASSEX);
WindowClass.style         = CS_HREDRAW | CS_VREDRAW;
WindowClass.lpfnWndProc   = Win32MainWindowCallback;
WindowClass.hInstance     = Instance;
WindowClass.hCursor       = LoadCursor(0, IDC_ARROW);

WindowClass.hIcon         = LoadIcon(Instance, "Icon");
WindowClass.hIconSm       = LoadIcon(Instance, "IconSmall");

WindowClass.lpszClassName = "BasicWindowClass";


Concluding thoughts

I've shown how I include data in my executables on Windows and with a platform-independent method. I default to using the platform-independent method unless there's a good reason to use something else (like the special treatment icons get as 'Resources'). Other people I know just put everything in the resource files as they're only/primarily targeting Windows, and the RC files keeps everything in one place. There doesn't seem to be much difference in speed at compile- or run-time.

Please do let me know if you attach files to your executable with these methods or if you have any related tips to share.
Andrew Reece
It's now a little over one year since the first commit on Geometer.
The process has taught me a lot, so I thought I'd give a quick overview of some of the things I've learnt, as well as hint at some future blog posts.

Contents
  • Project strategy
  • Version Control
  • Process of writing code
  • Invalid array indexes
  • Enums
  • Macros
  • Saving and loading binary files
  • Linear memory undo
  • Geometry/maths
  • Complex state-based user input
  • UI Feedback
  • Multiple monitors
  • Resources
  • Common/notable bugs

Project strategy
  • It's difficult to find time to work when moving to a new area and starting a new full-time job
  • Weekends always seem like they'll have loads of time, but social/admin obligations often seem to pop up.
  • The most productive time for me seems to be in the mornings, before work and after a cold shower, when I'm freshest.
  • Don't prioritize a few more minutes of programming over exercising/eating/sleeping. You will be less productive long-term if you're not healthy.
  • I chose to prioritise writing code over blog posts when I had time (for better or worse).
  • Deadlines help focus - I'll now be posting on the blog each Monday for the rest of April.
  • It takes me a few minutes to work out where I am and what needs doing from looking at the code cold, but whenever I finish, I almost always have an idea of where to go next. I've started to adopt Hemingway's unfinished sentence idea for code: I leave a statement that will fail to compile, either by missing out a semicolon, or just giving myself a few words to describe the next step that aren't commented out. I then just compile straight after firing up Vim to see where I'm at.
  • Write the simplest thing that will compile in a way you can 'test'. It's normally better to take a few testable zigs and zags rather than try to go linearly to the endpoint. When (not if) that fails, there's much more code that you need to go through to find the bugs.
  • Try and test the program on one other machine before releasing, or failing that, with the executable in a directory by itself. It's not a great look to have the first comment on a release you're excited about to be "It crashes on opening" (ask me how I know).

Version Control
  • Use it. Commit regularly.
  • Each commit on the master branch should run properly (and pass tests ahem, something I need to do more), partial checkpoints should go in branches.
  • It's useful to know what version of Geometer people are using (particularly when there are bugs).
    I want this to be both human-readable (i.e. not a SHA) and directly identify a commit for me to investigate. git describe --tags is an easy way to do this.
    • I wrote a post-commit script to add a version tag for each commit (which I cancel with ctrl-c if unnecessary):
      1
      2
      3
      4
      5
      6
      7
      #!/bin/sh
      # TODO: check that we're on master
      echo
      git log --oneline --decorate --reverse -4
      read -p "Tag name: v0." tagname </dev/tty
      git tag v0.$tagname
      echo
      
    • This is added (somewhat awkwardly) as a define in the build script:
      1
      2
      3
      for /f "tokens=* USEBACKQ" %%f in (`git describe --tags`) do (
      set VersionNum=%%f)
      cl win32_geometer.c ... -DVERSION_NUMBER="%VersionNum%" ...
      
    • I then just include this into my assert messages: "Version number: " VERSION_NUMBER "\n\n"

Process of writing code
  • Whenever I feel the need to comment, I try and instead add better-named intermediate variables. This normally obviates the need for comments, and won't get stale.
  • Just about everything is written inline until it is repeated at least once (see John Carmack's comments on long/inline code).
    • Logical blocks are scoped with curly braces to minimize accidentally making separate bits of code inter-dependent.
    • This approach also makes it really easy to extract blocks into functions when they're used multiple times.
    • Scopes have a comment describing what they do in a single sentence at the first brace, so that you can fold blocks and see what it happening at an appropriate level of abstraction
  • I experimented a bit with Hungarian notation. Not worth adopting wholesale, but I did find it useful to prefix some common constructs, e.g. i____ for array indexes, d____ for differences, c____ for counts, t____ for time values. I've also used it to distinguish concepts that I'm too lazy to differentiate with proper types, e.g. Points and Vectors - see Joel on Software's post on Making Wrong Code Look Wrong for some other examples.

Invalid array indexes
I was doing some queries into point arrays and started using 0 as an invalid index. This meant that I could do standard boolean conditionals such as if(SnapPointIndex) { DoThingWithSnappedPoint(SnapPointIndex); }. It also meant that I had to keep the first point free. I now have a mix of 0-index and 1-index arrays, which has lead to a few off-by-one errors, and just adds unnecessary cognitive overhead.
In future I'll be using enum { INVALID_INDEX = 0xFFFFFFFF };, which requires a little more typing, but simplifies everything else...


Enums
  • Have a simple incrementing version: this is useful as an index for strings etc, and easy to get a count (see below). If you're using flags, make a simple incrementing version as well (see below).
  • Consider having 0 as an invalid type, so you can use if(Thing.EnumKind){...} constructs
  • You can make groups with outer bounds (see below), and check for membership with (SHAPE_BEGIN_Linear <= Kind && Kind <= SHAPE_END_Linear).
  • Bitflags and string labels can be made easily (see X-macros below)
  • Negatives (this obviously does not apply to 0) are useful for holding an extra bit of information (for normal enums) in a way that's easy to read and write. e.g. negative shapes are not shown to the user.

Macros
  • Used judiciously, they can help readability and maintainability.
  • X-macros are particularly useful, as long as you can group multiple 'statements' together in your code.
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #define SHAPE_TYPES       \
    SHAPE_TYPE(SHAPE_Invalid) \
    SHAPE_TYPE(SHAPE_Line)    \
    SHAPE_TYPE(SHAPE_Ray)     \
    SHAPE_TYPE(SHAPE_Segment) \
    SHAPE_TYPE(SHAPE_Circle)  \
    SHAPE_TYPE(SHAPE_Arc)     \
    
    #define SHAPE_TYPE(name) name,
    typedef enum {
    SHAPE_TYPES
    SHAPE_COUNT,         /* useful if you need to loop over them */
    /* Groups: */
    SHAPE_BEGIN_Linear = SHAPE_Line,
    SHAPE_END_Linear  = SHAPE_Segment,
    } shape_types;
    #undef SHAPE_TYPE
    
    /* If these weren't sequential, you could still get a count: */
    #define SHAPE_TYPE(name) +1
    enum { SHAPE_ALT_COUNT = SHAPE_TYPES };
    #undef SHAPE_TYPE
    
    /* This assumes that they are sequential */
    #define SHAPE_TYPE(name) #name,
    char *ShapeTypesStrings[] = { SHAPE_TYPES };
    #undef SHAPE_TYPE
    /* Used as: printf(ShapeTypesStrings[Shape.Kind]); --> "SHAPE_Arc" */
    
    /* I don't need flags for my shapes, but if I did...: */
    #define SHAPE_TYPE(name) name ## _FLAG = 1 << name,
    typedef enum { SHAPE_TYPES } shape_type_flags;
    #undef SHAPE_TYPE
    #undef SHAPE_TYPES
    
  • Debug - a number of debug features can be added by appending information into static buffers, as in live_edit.
  • Common accesses that change approach often: I've changed the way that I access points a few times now: basic array access, through an additional layer of undo state, through a dynamic array, and then with checked bounds access. At some point I realised that it was easier to just use POINTS(PointIndex) and redefine that as needed. I'm not particularly consistent with this though...
  • Adding 'features' to C:

Saving and loading binary files
(I'll be doing a blog post just about this, particularly on issues around versioning)
  • The process of doing this helped me better think about data as just a series of bytes in memory - a useful perspective to be able to take.
  • Enum labels for file sections etc must be unique and unchanging after a version goes public - make them append-only in a separate file
  • The file format, particularly the header should let you:
    • Determine that it's your filetype
    • Tell what version it is so that you can read it the right way
    • Error check the file (for corruption)
    • Read a useful amount of data into memory in one go (most likely the whole file)

Linear memory undo
  • My initial approach to memory was to just keep a rolling buffer of states. This is safe and easy, but is both O(n^2) and makes accessing memory verbose.
  • I had a rethink in terms of user/program actions (I'll write more about this at some point).
    • I save just enough to reconstruct the state at each action going either forwards or backwards in history.
    • This granularity doesn't match a user's mental model, so I tag some of the actions as 'user actions' (whether the enum Kind for the action is positive/negative) and undo/redo to these.

Geometry/maths
  • Software rendering shapes has some interesting challenges (see my thought process for drawing lines)
  • Finding intersections was harder than I expected. A couple of game maths books and some online searches did me fine though (I'll write some examples of the harder parts).
  • My intuition for linear algebra has improved a lot by working with it.
  • Working out the maths for bases by hand both helped my understanding, and allowed me some optimisations from not needing the most general case.

Complex state-based user input
The first pass on UI involved switching on the input used and dealing with ad-hoc state within these levels. This became complex and order-dependent as the number of states and input grew.
Switching on more reified levels of state and then dealing with actual input simplified this a lot. I deal with a couple of inputs up-front that relate to all states - notably escaping from drawing states and panning around. The basic structure is roughly as follows:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
if(IsPressed(C_Cancel))
{
    ReturnStuffToNormal(State);
    State->InputMode = MODE_Normal;
}

else if(IsPanning)
{
    /* Pan */
}

else switch(State->InputMode)
{
    case MODE_Normal:
    {
        if(IsPressed(C_StartLine))
        {
            if(C_PointsOnlyMod.EndedDown)
            { State->InputMode = MODE_DrawPoint; }
            else
            {
                State->LineStartPoint = CanvasMousePos;
                State->InputMode = MODE_DrawLine;
                goto input_mode_drawline;
            }
        }
        /* ... */
    } break;

    case MODE_DrawLine:
    input_mode_drawline:  /* calculation for the preview is done here. This is an easy way to avoid */
    {                     /* the preview being drawn with junk data without adding extra calculation */
        /* ... */
    } break;

    /* ... */

    default:              /* always have a default case for switches, even if it should never be hit */
    { Assert(! "Unknown input mode"); }    /* the ! makes the assertion fail */
}


UI Feedback
(I'll be writing more about this)
  • Make it obvious what the current state of the system is.
  • Sudden jumps by continuous variables can be confusing.
  • Lerp (interpolate) between states to make clear both what changed and how it did so.
    • This can be very fast and still be effective.
    • Use a float between 0.0f and 1.0f to track animation state. Set this to 0 on triggering the animation.
    • You probably want to clamp to these values and/or assert if it's outside. I've had a couple of bugs from very large t-values making floats get so big that x+1.f == x, and so some loops never finish.
    • 2 easy uses for lerps:
      1. the linear interpolation: fix the start and target value when triggering the event.
      2. the decaying interpolation: do the same, but each frame reset the start value to be the current position.
    • There are a bunch of fancier motion curves that you can use.
    • A simple ease-in and ease-out curve that looks good and is really quick to compute is SmoothStep:
      1
      float SmoothStep(float t) { return 3*t*t - 2*t*t*t; }    /* 3t^2 - 2t^3 */
      
    • See http://easings.net/ for other examples. There is C code for these here: https://github.com/warrenm/AHEasing/blob/master/AHEasing/easing.c
    • See Casey's video on interpolation.

Multiple monitors
They're a thing - don't forget to account for them.


Resources
  • On Windows, use .rc files for icons
  • Use xxd for everything else.
    • xxd can output an array of bytes in a C header file, along with the length of the array.
    • Use this to easily include any arbitrary resource.

  • Common/notable bugs
    • Arena out of bounds - caught by my runtime bounds checking.
      • Occasionally an arena problem, e.g. the length hasn't been set.
      • Normally something else has gone wrong in the algorithm, and this is the first thing that triggers.
    • Float precision
      • Very small differences in value from float imprecision meant that I was unintentionally adding multiple points to almost exactly the same place. To fix it, I had to check that float values for point locations are checked within a given epsilon (small error range). Moving to fixed point might be a better solution, but I haven't tried it yet.
      • As mentioned above, floats getting so large (normally from another bug) that x+1 == x. Some of my drawing loops are based on adding 1 to a vector dimension, and so never finish if the values get too big. In some cases integer types might be more appropriate, otherwise you can just assert for this.
    • Not keeping cached versions of information in sync with the canonical version. Avoid storing a copy of data or trivially-derived data (e.g. LengthInMm, LengthInM) unless you have a good reason.
    • The debugging process itself(!) I sometimes forget about the first thing I've tried when figuring out why something isn't working, so after hardcoding a test value, I try some other stuff and take a while to realise why it's not varying as expected. I've already gone through things in the debugger and feel like I've built a representative mental model, but this doesn't include my ad-hoc tests. These are probably the least satisfying bugs to find - you've just been wasting your own time.
    • Copy-pasting code
      • In particular copying for loops on arrays with similar names and contents, then not changing all of the names.
      • I fixed this with some foreach macro constructs, which also make the code more readable.
        The difference is more pronounced when they're nested with similar names.
         1
         2
         3
         4
         5
         6
         7
         8
         9
        10
        11
        12
        13
        14
        /* before: */
        for(uint iTestPoint = 0; iTestPoint < Len(State->SelectedPoints); ++iTestPoint)
        {
            uint TestPoint = Pull(State->SelectedPoints, iTestPoint);
            if(PointInAABB(POINTS(TestPoint), SelectionAABB))
            { Remove(&State->SelectedPoints, iTestPoint--); }
        }
        
        /* after (gives the index with an i prefix): */
        foreach(uint, TestPoint, State->SelectedPoints)
        {
            if(PointInAABB(POINTS(TestPoint), SelectionAABB))
            { Remove(&State->SelectedPoints, iTestPoint--); }
        }
        
    • Using typeof(type) rather than the longer but less brittle typeof(Struct->Member.SubMember). The former can fail in non-obvious ways if you change the variable's type.
    • The bug that took me the longest to find showed up as text in the memory for my input handling code. I found a few things that needed fixing in the process of hunting this down.
      • The main problem was that I was reallocating a void-pointered in an arena, and hadn't updated a matching typed pointer that I was using.
      • A lovely combination of cache invalidation, improper memory access, and a non-obvious trigger (enough intersections to cause reallocation).
      • I now used typed arenas (which I make with a macro) that union a void pointer, a u8 pointer and the type I want:
      • 1
        2
        3
        4
        5
        6
        7
        /* ... */
        union {
        void *Base;
        u8 *Bytes;
        user_type *Items;
        }
        /* ... */
        
        I should probably transition this to dynamic arrays/stretchy buffers (as described above), as that is how I'm using the arenas.

    Conclusion
    Ok, I'm over 2500 words now... this is probably getting long enough. Please let me know if any of these are useful to you or you'd like me to write more about them.