2007-10-25

Buttons, Text, Events and Stuff

I was tinkering with the Woopsi documentation earlier, writing a section about the TextViewer, when I realised that the TextViewer had a design flaw - it used twice as much memory as it needed to.

When the constructor or setText() function is called, the TextViewer class runs the text through a word wrapping function, splitting it into individual lines and pushing those lines into a vector. This gives it pre-formatted text data to work with later for display. However, it doesn’t really split anything - it creates a copy of each line of text and stores the duplicate in the vector. This means that, once the wrap function has finished running, the TextViewer class contains a complete copy of the original text split into chunks. If we send it 2MB of text, the TextViewer will contain a pointer to the original (2MB) of text, plus the duplicate text (2MB plus any overheads associated with the vector class). It wastes vast amounts of memory.

I had a think about this, and decided that I didn’t actually need to copy the text. If I scrapped the text vector and replaced it with a vector that stored the offsets of the start and end of each line of text (as a struct), I’d need to store only 8 bytes (two 32-bit integers) per line instead of around 32 (maximum number of characters per line for an 8x8 font). Thinking about it some more, I could store the start offset (4 bytes) and line length (1 byte) instead of the start and end addresses, and save a further 3 bytes. If our 2MB text file consists of one long line of ASCII it’d contain 2,097,152 characters, or 65,536 lines of DS-formatted text. Each line consumes 5 bytes of mapping data in the vector, which totals 320K of wasted memory (plus overhead, natch) instead of 2MB.

Implementing this change was simple enough, and it should make things a tiny bit quicker, too.

Following on from Jeff’s comment that highlighted the problems with functions that sometimes do what they’re called and sometimes do something entirely different, I’ve fixed the inconsistent behaviour of the gadget close function - it now closes and marks a gadget as deleted, instead of changing its function depending on the situation. I’ve also added the missing events - close, hide and show.

Another idea for a new Woopsi feature - animated buttons. It would be fairly easy to change the BitmapButton class so that it contains a sequence of frames for each clicked state instead of just a single image. I’d need to write an Animation class that has various options, such as playback speed and loop type (none, loop, ping-pong), and I’d just drop that into the button in place of the current single bitmap.

Finally, it seems Nintendo read my blog, because they’re apparently considering releasing a flash cart of their own. Assuming they release some sort of dev kit for it that lets me get at the hardware, code in C++, and isn’t just a cheap copy of SEUCK, I’ll buy it as soon as it’s available.

Comments

Jeff on 2007-10-26 at 00:53 said:

Why do you need the length of each segment? After all,

len(line3) = start(line4) - start(line3) + 1

Jeff on 2007-10-26 at 00:57 said:

One other question - why store the line starts at all. If you just maintained an array of length bytes, then the only issue is how to find the start of line (n) - line (n-1) is just the start of line(n)-length(n).

At the start, you know where line(0) starts (position 0). To find line(1), just add len(0).

Yes, its slow if you want to find where line(65000) starts, but is that really an issue? I don’t know why you need to do that, other than for draw operations, and if you cache the index of the top-line on the screen, the rest should be relatively simple. Scrolling back a line is just a subtract. Scrolling back 100 lines is just 100 subtracts?

(Note: I haven’t thought this through fully, it just came to me while reading your post)

ant on 2007-10-26 at 06:30 said:

I have both start and length because if I split at a space/line return, I don’t want to print the last character, but if I can’t find a place to break and split at the maximum length position, I do want to print the last character.

Thinking about it, the first situation would probably be better handled in the font writer. If I make it intelligent enough to identify empty glyphs in the font, the whole text printing system would work faster.

Jeff on 2007-10-26 at 10:14 said:

Hmmm, to be honest, I’m not convinced but then again, you don’t need to convince me. Unless you are doing a fully-justified output, it seems like you should already be trimming off trailing spaces from each line (but being careful to erase whatever else is already there) irrespective of the length of the line you were asked to output. So you could still get away with just recording the lengths, I think.

Having said that, what happens if you split at a run of space. ie, if you choose to split between here> and printing the rest on the next line? Or collapsing all white-space the way that HTML does, and suppressing them all? That’s going to catch people out when they try to output multiple spaces and find that they don’t seem to stick.

In my opinion, I’d be inclined to have the text writer widget TRUNCATE long lines - if the application wants to have them wrap, the application should insert its own soft-returns, but it shouldn’t happen by default in the lowest level text gadget.

Jeff on 2007-10-26 at 10:15 said:

Oh crap, html again. I tried to say:

Having said that, what happens if you split at a run of space. ie, if you choose to split between here>   <and here, will you be suppressing the first space after the > and printing the rest on the next line?

ant on 2007-10-26 at 11:18 said:

I had a look at just maintaining a list of lengths, and it quickly gets far too complicated to justify the time it’ll take to code (at present, anyway - I can always revisit it later if necessary). I’m going down the route of just storing line start positions.

I won’t get the text output system to ignore spaces - all I’ll do is tell it to not bother trying to output a glyph if the glyph doesn’t contain any visible data. As each glyph is written pixel by pixel to the screen, an 8x8 blank space in a font uses 64 read operations per write attempt that don’t result in any changes being made. If the font’s constructor can build up a map of which glyphs are populated and which are empty, I can bypass those redundant write attempts.

This isn’t to say that I won’t leave spaces where spaces should be - I just won’t bother trying to write those spaces to the display.

I think there might be a bit of confusion here, introduced by me assuming that everyone else is as familiar with the code as me. The TextViewer is the gadget that can display large amounts of text. The TextWriter, on the other hand, is a utility class that actually copies font glyphs to the DS’ framebuffer.

The TextWriter doesn’t wipe anything before writing text - this lets me put text on top of another image without a surrounding background colour. Wiping the area that text will be written to is the responsibility of the gadget using the text writer. In the case of the TextViewer, scroll operations use the DMA copier to shift the existing text about, then I draw a filled rectangle over the region that will contain new text (wiping it), then I use the TextWriter to output the new rows of text. As I scroll the contents of the whole gadget’s rectangle, old rows get overwritten by new rows automatically, and empty space also gets copied around.

Regarding runs of spaces, white space does not get supressed. Similarly, trailing spaces aren’t trimmed. I can see arguments both ways, but I just prefer to have the text displayed accurately. If I change the font so that it displays a retro-style box as a space, and do some funky ASCII art with my text, I’d get annoyed if the TextViewer stripped out my funky boxes at the end of each row.

Not sure about truncating long lines - having to write wrapping routines is a pain, so I’d prefer to have it available by default. I can’t imagine a situation in which I’d particularly want to have long lines truncated rather than wrapped. The DS’ screens are so small that barely anything would be visible.

Finding a split point is a two-pass algorithm. Say we have a char array that is 20 characters long, and we have a maximum line length of 5 characters. First of all, we need to scan for a line return, so we start at the left of the text and work towards the right. If we hit a line return before we hit the maximum line length, we store the position of the next character after the return as the start of the next line.

If we don’t find a line return, we go for the second pass, and hunt for other breaking characters (ie. spaces). This time, we start at the right of the line (line start + max length) and work towards the left. The first breaking character we encounter gives us a break point, so the next line starts at that position + 1.

If we have a run of spaces that encompass the max line length position, the run of spaces will get split. Anything before the max length position will appear on the top row, and anything after the max length position will appear on the second row - the second row will, therefore, appear to be indented.

I could probably merge those two passes into a single pass. I might look into that…

Jeff on 2007-10-27 at 00:44 said:

An approach I’ve used in the past to avoid the ‘two-pass’ requirement is to have the first pass remember the position of the most-recent space character, while searching for the newline. Thus, when it discovers that its run out of room, it does’t need to re-scan, it knows what the backup point is already.

ant on 2007-10-27 at 07:39 said:

Aha, that’s exactly the approach I took.