Fast undo facility for bitmap editor application

Question

I'm trying to make a bitmap editor app for the iphone which would be similar to Brushes or Layers or a cut-down version of Photoshop. I'd like to be able to support 1000x1000 resolution images with about 4 layers if possible.

I'm trying to design my undo/redo system before I write too much code and I'm having real issues coming up with a good solution because of the limitations of a mobile device and the fact that bitmap editor operations are usually destructive. The most common undo/redo designs I know of are:

1. Use the command pattern. You store the initial state and the commands used to transform this to the current state. To undo, you reload the initial state and replay all the commands except for the last one.

2. Use the memento pattern. After each operation, you store enough information to be able to revert that operation.

The problems I foresee are:

1. Command pattern: What do I do after 500 edit operations and I want to undo the last one? Loading the initial state and applying 499 could be time consuming especially if some of these are costly things like e.g. applying blur filters. I don't like the way undoing takes a different amount of time under different scenarios.

2. Memento pattern: Saving the parts of the bitmap that were modified takes a lot of memory. Caching these bitmaps to disk can be slow as well (so I might have trouble caching the bitmaps if the user is making lots of fast edits) and I'm not sure about the battery usage implications.

The only solutions I can think of are:

1. Use the command pattern and memento pattern where, every 10 commands or so or after an expensive operation, the whole state is also saved (which gives you an autosave feature for free). To undo, I reload the closest snapshot and then replay the commands. I'd rather avoid this complexity though.

2. Use the memento pattern and force the user to wait for the bitmaps to be cached. This isn't too bad if I build this time into e.g. waiting for a filter to apply but it doesn't work well between making brush strokes.

Are advice? I'd be interested to know how some existing apps do this.

I can think of all sorts of weird hybrids of the above but they all have obvious problems. All I can think to do is live with some of these problems or compromise the app to make the problem simpler (e.g. reduce the size of the maximum bitmap size). I have noticed that several apps have quite low maximum bitmap sizes and layer limits.

Answer 1

Checkpoint each bitmap with memory mapping The flash memory on iOS devices is fast enough to support undo/redo operations on large bitmaps. Using the mmap system call, I memory mapped 1024x768 ABGR bitmaps with ease, saving my program from using precious DRAM. I don't know how you would like to abstract the undo/redo patterns but the way to avoid any high-overhead copy operations is to have the pointers for undo and redo bitmaps swap each undo/redo. You have specified more than one undo level, but I bet you can get away with some pointer swapping (I am suffering from some insomnia right now and trying to demonstrate the pointer swapping proved too much--it was some pretty garbage psuedocode).

Also, I would not recommend marking your mmap'd pages as F_NOCACHE. It is preferable to have iOS cache writes to the bitmap in DRAM because:

• It's faster if you don't flush to flash
• Flash memory is designed for a fixed number of writes--it's not nice to burn out users' flash (I think it takes somewhere on the order of 5 million writes with the quality flash in iOS devices)
• I believe iOS is aggressive enough in memory management that it will unmap your cached writes and flush them during a memory crisis (I never cared enough to check, though)

Shout out to John Carmack for the tip-off that the iDevice Flash memory is quite fast (He uses F_NOCACHE, though, to get predictable read performance).

Note that I had to make the file be the size of the actual bitmap before calling mmap on the fd. Don't go nuts memory mapping 100 bitmaps, though (just kidding--DO IT!) I mean, how many undos can a user perform? They are weak and their fingers get tired after mere seconds of button-mashing.