3
\$\begingroup\$

I'm building a PIC-based text editing 'laptop'. I have an SD card connected to the PIC and am using a keyboard and an LCD screen.

My problem is that I want to edit real big files like for example over 300kB. Now I have some options for the memory control:

  1. Store the whole file in extern RAM. Inserting new characters in the middle of the file will result in replacing every byte to one address higher. Disadvantage: speed, since replacing 300,000 bytes will take some time.
  2. Store bytes address-based in extern RAM. Separate the RAM into two halves: one contains the addresses for the bytes in the other. Inserting characters would mean adding bytes to the end of the second half, and adding the addresses to the end of the file to the first half. Disadvantage: not so efficient RAM usage, would take a long time to save the file in the end since all the addresses are spread through the RAM.
  3. Something with a gap buffer in extern RAM, so that would mean leaving NUL characters on the SD card available for future insertions. Disadvantage: not so efficient SD card usage, however this is not a problem. Also: hard to code(?).

My question: I'm thinking about the gap buffer to implement, however I might miss something. Is a gap buffer the best way to do this?

\$\endgroup\$
  • 5
    \$\begingroup\$ Besides here, the StackOverflow folks might find the question interesting. \$\endgroup\$ – Anindo Ghosh Jan 12 '13 at 10:36
  • \$\begingroup\$ Good point, I'll copy it to there as well. \$\endgroup\$ – Keelan Jan 12 '13 at 10:37
  • \$\begingroup\$ Why do options 1 and 2 assume external RAM, while option 3 does not? Using the gap buffer technique with the external RAM would actually work quite nicely. \$\endgroup\$ – Dave Tweed Jan 12 '13 at 12:58
  • \$\begingroup\$ Ehm, edited my post, I meant a gap buffer in extern RAM. Thanks for noticing :-) \$\endgroup\$ – Keelan Jan 12 '13 at 12:59
  • \$\begingroup\$ even though @AnindoGhosh suggested it, the sites consider it abuse to post the same question multiple places. you should tailor a question to the audience and should not just post it everywhere at once. \$\endgroup\$ – Kortuk Jan 12 '13 at 16:53
3
\$\begingroup\$

My first reaction would be to use a large external RAM to keep the data being edited in. But instead of making that a direct image copy, I would pre-allocate blocks of RAM in a linked list. Each block would have a forward pointer, backward pointer, used size, and the fixed-size data buffer.

Make each block a power of two bytes in size. That means the low few address bits for each block are known to be 0, so don't need to stored. The forward and backward pointers could then be 16 bits and the used length 1 byte, for a total of 5 bytes overhead per block. With 32 byte blocks, for example, this represents 16% overhead. 1 Mbyte of RAM would yield 885 kBytes of actual data storage, well more than the 300 kBytes you asked for.

In effect, this scheme creates a linear memory that can have data inserted or deleted at arbitrary places with little overhead. When adding or deleting, you don't have to look past the adjacent blocks in the chain, so can easily be done instantaneously in human time.

You keep two chains, one for the blocks holding the data and one for the unused blocks. Just the right kind of editing in just the right places could cause so much fragmentation overhead as to make the memory look much smaller, and eventually unable to hold 300 kBytes. However, such specific editing is unlikely to occur, and you can always do simple local recombinations (if two adjacent blocks hold less data than one block, then merge the two and put one back on the free list) which will most of the time keep fragmentation down well enough. Fragmentation doesn't actually matter until you need a free block and there isn't one. When that happens, you do a defrag and the user has to wait a few seconds, but this will be very rare. A good strategy would be to do automatic defrag in the background during the inevitable long periods of time (from the processor's point of view) where the user is doing nothing. With this strategy, I think it's very very unlikely you ever run out of free blocks and have to defrag while the user waits.

This scheme is easy to manage even in a small microcontroller, user response to editing operations is fast, and the SD card is only accessed at the start and end of editing sessions.

Added:

I was considering fragmentation more after writing the post, and I think it can be shown that as long as you do simple local defrag on any insert or delete operation, you never loose more than 1/2 of the available memory. Using the 1 Mbyte memory with 32 byte blocks example again, you are guaranteed at least 442 kBytes of storage.

After a delete, you merge the block that had a byte deleted with one of its neighbors if the two together now hold one block worth of data or less. On a byte add, you flow data from the current block into a neighbor to make room instead of grabbing a new block unless both neighbors (and of course the current block) are completely full.

All these operations never envolve more than 3 blocks, so are instantaneous in human time. If you can live with up to half the available memory unused, then you don't need to do anything further. There is little harm in doing background defragging though when nothing else is going on.

\$\endgroup\$
  • \$\begingroup\$ Also an interesting solution! Just to make sure I understand this: isn't this the same as how the FAT file system works? \$\endgroup\$ – Keelan Jan 12 '13 at 15:43
  • \$\begingroup\$ @Camil: I can't say as I never looked into FAT at that detail. \$\endgroup\$ – Olin Lathrop Jan 12 '13 at 15:49
  • \$\begingroup\$ Okay, then I will assume it, as I've reread your post and the specification. It's a great idea and I certainly will take it into account! \$\endgroup\$ – Keelan Jan 12 '13 at 15:52
  • \$\begingroup\$ @CamilStaps: Olin's scheme is not at all like FAT. While FAT uses linked lists to keep track of clusters of data, it does not allow individual blocks (clusters) to have variable sizes. If you want to insert or remove data in the middle of a FAT file, you need to rewrite all of the data following that point. \$\endgroup\$ – Dave Tweed Jan 12 '13 at 16:22
  • \$\begingroup\$ Okay, because of the variable cluster size it is different, yes. It is a lot more flexible because of that. Interesting, interesting! :-) \$\endgroup\$ – Keelan Jan 12 '13 at 16:24
2
\$\begingroup\$

This is a basic programming problem that you can solve more comfortably on a PC without worrying immediately about the PIC, though obviously you will be looking for a small efficient solution!

Another approach - viable if you can specify a character or sequence that cannot occur in text - is to replace a few bytes in your text buffer (which could be external RAM) with that sequence followed by a number. This acts like a software breakpoint in a debugger : when File/Save sees that breakpoint, look up the number in a list of changes. It will contain the characters you removed plus any modifications.

If the list of changes gets full, you need to re-synchronise the document to empty the list; this could also be an autosave operation. (Up to that point, you also have an undo facility!)

You want to minimise the number of SD card writes - so only autosaves and user File/Save operations rather than writing every change to SD.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's a very nice approach and I'll certainly think this over! I might accept your answer, but will wait for others to come with other answers as well. \$\endgroup\$ – Keelan Jan 12 '13 at 11:45
  • 1
    \$\begingroup\$ Hold off accepting it for a few days, there may be other good answers. \$\endgroup\$ – Brian Drummond Jan 12 '13 at 13:46
2
\$\begingroup\$

For a simple text editor, the gap buffer method is very effective. I used it when I wrote an editor for my Ferguson Big Board (Z80-based CP/M) computer in the early 1980s, and I found it very easy to work with. Of course, I was able to use some low-level Z80 instructions that made it very efficient to move text across the gap.

This method also expands nicely to editing multiple files simultaneously, assuming they all fit together in the available RAM. You just concatenate them together, and the gap exists only in the file that currently has the editing "focus". You do need to keep some pointers (or markers) for the file boundaries, and deal with them as needed when moving the gap.

\$\endgroup\$
  • \$\begingroup\$ +1 for the idea of editing multiple files simultaneously! There are enough ASCII characters that can be used as markers for file boundaries. Thanks for the tip! \$\endgroup\$ – Keelan Jan 12 '13 at 15:05
  • \$\begingroup\$ @CamilStaps: I would actually caution against creating an editor that isn't "8-bit clean" (i.e., can handle arbitrary binary data). Perhaps your application is more restricted, but my editor was for general software development, and it is frequently useful to be able to open up an arbitrary file (even a binary file) for a quick look inside. In other words, I would recommend using pointers rather than markers (and not just for file boundaries). \$\endgroup\$ – Dave Tweed Jan 12 '13 at 15:12
  • \$\begingroup\$ Yes, that's a point. For the first version this will be just plain-text, so STX and ETX or special characters like 176 and higher would be OK, but for future compatibility it is a good idea to use pointers! :-) \$\endgroup\$ – Keelan Jan 12 '13 at 15:17
1
\$\begingroup\$

The external RAM usage is certainly the best scheme. A gap buffer can split the test stream into the lower half at one end of your memory pool and the upper half at the other side of the memory pool. Local inserts and deletes can then be done across the span of the gap simply by moving small amounts of data across the gap margin one way or the other.

The use of a gap buffer can be a good strategy to use in a dynamic way. You can focus on opening up a hole at the current edit focus location so that new data has a place to go. Initially you can place a re-direction tag at the focus location by removing just enough existing text to allow room for insertion of the tag. Then in a separate work buffer pointed to by the tag you can capture the initially removed text and then add any new text being typed in. With clever programming you can execute a parallel process that splits the in-memory image to update the the gap and then removes the redirection tag and temporary edit buffer associated with it. If movement of the edit focus point changes before the parallel process has had a chance to do its thing updating the gap you can simply create a new re-direction tag and allocate another work buffer from an available list.

This scheme allows for a list of re-direction tags (and their work buffers) to be dynamically reclaimed so that you would rarely get a "list full" condition. The premise being of course that during an editing session the average arrival rate of new data comes slower than the program can move the gap region around and reclaim the re-direction tags.

Another note regarding the idea of inserting tags into the text flow. Tags may also be used for other things than just marking where you have placed a re-direction tag. It can be a good idea to mark tags in such a way that you can find them in the text stream whether scanning forward or backwards through the text. The simplest of course is to embed the tag with the same tag indicator at each end.

\$\endgroup\$
0
\$\begingroup\$

A lot will depend upon the types of operations you need to perform. If you can store data temporarily as a list of fixed-length lines, you can use use a fixed-size chunk allocator to store the individual lines in arbitrary sequence, and then use a RAM array or gap buffer (possibly in an external RAM device) to convert linear line numbers to chunk locations. One could also use variable-length lines with a variable-length chunk allocator, or use fixed-sized chunks but have each chunk contain a number that either specifies the number of used bytes or the length of the next chunk. Use a RAM buffer to hold the current line, so that the chunk array only needs to be accessed when the cursor is moved off it. SD cards are sufficiently large that even if every line is padded out to 256 bytes in a temporary file, that probably shouldn't pose too much difficulty. Each 256 bytes would either contain an FF byte and a length, or a two-byte block number; that would allow for files of up to about 8 megabytes and 32767 lines.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.