Efficient algorithm for writing several bits across several words

One of my projects involves drawing text. The project is based around a mid-level 16-bit microcontroller, a dsPIC33FJ128GP802. It is capable of 40 MIPS, but about 92% of that is reserved for background processing (outputting an on screen display), so on average it gets 3 MIPS to render stuff. The processor has hardware multiply, assisted divide (18 cycles) and a full 16-bit barrel shifter.

The original method was simple. It just called the set pixel routine for each pixel that needed to be written, however, this is quite slow: each pixel write requires an address decode, bit mask, and write to memory - on average, around 60 cycles per pixel. Also, two bits need to be written for each pixel to be set: one in the mask array (which determines if the pixel is visible or not), and one in the level array (whic开发者_开发问答h determines if the pixel is white or black.) For a single character, 8x14 pixels, this means 13,440 cycles plus overhead. Which is a lot, given the lack of much processing power.

Because of this, I came up with an algorithm for drawing horizontal lines. It could efficiently write up to 16 pixels in about 20 cycles, which is a 60 fold improvement on setting pixels individually; it could also handle lines which did not lie on word boundaries (using some clever bit math), and even lines which lie entirely inside one word. (Note - one word is 16 bits and the video memory is stored as an 4 arrays of 3,072 words, a front buffer and back buffer.) I'm not certain if the algorithm is original - I doubt it - but for those curious, I've documented it here.

Now I'm racking my brains out trying to figure out a way to set multiple distinct pixels across multiple words. Ideally, it would work like this - we want to write this word starting at bit 4 (bits counted from zero) of the first word and allow it to overflow into the next:

Memory before : 0000 0000 0000 0000   0000 0000 0000 0000
Word to write : 1111 1010 1111 1111
Memory after  : 0000 0111 1101 0111   1111 1000 0000 0000

If anyone knows of any such algorithm or has done something in the past similar to this it would be great to know how you did it. I'm having a major brain block right now.

Can you rShift 5 bits, do an AND on the first WORD and then lShift 11 then AND on the second WORD or am I missing something?

In the days before sophisticated graphics accelerators, people hid whatever they could implement behind an interface such as bitblt. There is a quick write-up of one example of this in passing at http://swtch.com/~rsc/talks/drawtalk.pdf Some of these worked by auto-generating and then executing machine code. The approach from that paper is described as "Effectively, the draw implementation is the above with enough conditionals and function calls pushed outside enough loops to make the overhead bearable." One version I saw was quite long, with a variety of common special cases extracted "fast paths".