Эффективный алгоритм написания нескольких бит в нескольких словах

Question

Один из моих проектов связан с рисованием текста. Проект основан на 16-разрядном микроконтроллере среднего уровня, dsPIC33FJ128GP802. Он способен использовать 40 MIPS, но около 92% от этого зарезервировано для фоновой обработки (вывод на экран), поэтому в среднем он получает 3 MIPS для визуализации. Процессор имеет аппаратное умножение, вспомогательное деление (18 тактов) и полный 16-разрядный сдвиг барреля.

Оригинальный метод был прост. Он просто вызывал подпрограмму set pixel для каждого пикселя, который нужно записать, однако это довольно медленно: для каждой записи пикселей требуется декодирование адреса, битовая маска и запись в память - в среднем около 60 циклов на пиксель. Кроме того, для каждого устанавливаемого пикселя необходимо записать два бита: один в массиве маски (который определяет, видим ли пиксель или нет) и один в массиве уровней (который определяет, является ли пиксель белым или черным). Для одного символа 8x14 пикселей это означает 13,440 циклов плюс накладные расходы. Что очень много, учитывая отсутствие большой вычислительной мощности.

Из-за этого я придумал алгоритм рисования горизонтальных линий. Он может эффективно записывать до 16 пикселей примерно за 20 циклов, что является 60-кратным улучшением индивидуальной настройки пикселей; он также может обрабатывать строки, которые не лежат на границах слов (используя некоторую умную битовую математику), и даже строки, которые полностью лежат внутри одного слова. (Примечание: одно слово составляет 16 бит, а видеопамять хранится в виде 4 массивов из 3072 слов, переднего буфера и заднего буфера.) Я не уверен, является ли алгоритм оригинальным - я сомневаюсь в этом - но для любопытных, Я задокументировал это здесь .

Теперь я ломаю голову над тем, чтобы найти способ установить несколько разных пикселей для нескольких слов. В идеале это будет работать следующим образом: мы хотим записать это слово, начиная с бита 4 (считая биты с нуля) первого слова и допустить его переполнение следующим:

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

Если кто-нибудь знает о каком-либо из таких алгоритмов или в прошлом делал что-то подобное, было бы здорово узнать, как вы это сделали. У меня сейчас большой мозговой блок.

Answer 1

Можете ли вы сдвинуть 5 бит, сделать И для первого СЛОВА, а затем СМЕНИТЬ 11, затем И для второго СЛОВА или я что-то упустил?

Answer 2

Во времена, когда еще не было сложных графических ускорителей, люди скрывали все, что могли реализовать, за интерфейсом, таким как bitblt.Существует один быстрый пример написания этого примера: http://swtch.com/~rsc/talks/drawtalk.pdf Некоторые из них работали путем автоматической генерации и последующего выполнения машинного кода.Подход из этого документа описывается как «Фактически реализация вышеизложенного является вышеупомянутой с достаточным количеством условных выражений и вызовов функций, выдвинутых за пределы достаточного количества циклов, чтобы сделать накладные расходы переносимыми».Одна версия, которую я видел, была довольно длинной, с различными частными случаями, выделенными как «быстрые пути».