여러 단어에 여러 비트를 쓰는 효율적인 알고리즘

Question

내 프로젝트 중 하나는 텍스트 그리기입니다. 이 프로젝트는 중간 수준의 16 비트 마이크로 컨트롤러 인 dsPIC33FJ128GP802를 기반으로합니다. 40 MIPS가 가능하지만 그 중 약 92 %는 백그라운드 처리 (화면 디스플레이 출력) 용으로 예약되어 있으므로, 평균적으로 3 MIPS가 렌더링됩니다. 이 프로세서는 하드웨어 곱셈, 보조 디바이드 (18 사이클) 및 완전한 16 비트 배럴 쉬프터를 갖추고 있습니다.

원래의 방법은 간단했습니다. 그것은 단지 작성해야 할 각 픽셀에 대해 설정된 픽셀 루틴을 호출했지만, 이것은 매우 느립니다. 각 픽셀 쓰기에는 주소 디코드, 비트 마스크 및 메모리에 쓰기가 필요합니다 (평균적으로 픽셀 당 약 60 사이클). 또한 마스크 배열 (픽셀이 표시되는지 여부를 결정 함)과 레벨 배열 (픽셀이 흰색인지 검은 색인지를 결정하는)에 각각 하나씩 두 개의 비트를 설정해야합니다. 단일 문자, 8x14 픽셀의 경우 13,440 사이클과 오버 헤드를 의미합니다. 많은 처리 능력이 부족하여 많은 부분이 있습니다.

이 때문에 나는 수평선을 그리기위한 알고리즘을 생각해 냈습니다. 그것은 효율적으로 약 20 사이클에서 최대 16 픽셀을 쓸 수 있으며, 픽셀을 개별적으로 설정하면 60 배 향상됩니다. 그것은 또한 단어 경계 (거짓 비트 수학을 사용하여)에 있지 않은 선들과 한 단어 안에 완전히있는 선들을 처리 할 수 ​​있습니다. (참고 - 한 단어는 16 비트이고 비디오 메모리는 3,072 단어, 프론트 버퍼 및 백 버퍼의 4 개 어레이로 저장됩니다.) 알고리즘이 원래인지 확실하지 않습니다 - 의심 스럽지만 - I've documented it here.

이제 여러 단어에 여러 개의 서로 다른 픽셀을 설정하는 방법을 알아 내려고 노력하고 있습니다. 이상적으로는 다음과 같이 작동합니다 - 우리는 비트에서 첫 번째 단어의 4 (0부터 계산 비트)를 시작하는이 단어를 쓰고 싶어하고에 오버 플로우 할 수 있도록 다음 :

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 비트를 rshift 할 수 있습니까? 첫 번째 단어에 AND를 걸고 11 번째 Shift를 누른 다음 두 번째 단어에 AND를 넣거나 뭔가 빠졌습니까?

Answer 2

정교한 그래픽 가속기가 나오기 전에 사람들은 bitblt와 같은 인터페이스 뒤에 구현할 수있는 모든 것을 숨겼습니다. 이들 중 일부는 자동 생성 후 기계 코드를 실행하여 작동합니다. http://swtch.com/~rsc/talks/drawtalk.pdf 그 논문의 접근법은 "효과적으로 그려진 구현은 위의 것입니다. 오버 헤드를 견딜 수 있도록 충분한 루프가 외부로 푸시되었습니다." 필자가 보았던 한 버전은 꽤 길었고, 다양한 특수한 경우가 "빠른 경로"로 추출되었습니다.