« Previous : 1 : ... 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : ... 29 : Next »

디지털 컴퓨터는 전자 신호로 0과 1만을 인식할 수 있다. 그렇기 때문에 컴퓨터에서는 문자 역시 0과 1의 조합인 숫자로 표현되며, 문자를 그런 숫자에다가 대응시키는 규칙이 바로 문자 코드이다. 정보 교환을 원활히 하기 위해서는 보내는 쪽과 받는 쪽이 모두 문자 코드가 통일돼 있어야 함은 두 말할 나위가 없다.

정보량의 최소 단위는 1비트이지만 현실적으로 컴퓨터의 기억 장치들이 한 글자로 취급하는 정보량의 최소 단위는 8비트, 즉 바이트이다. 8비트, 2^8승, 즉 256이라는 정보량은 숫자와 알파벳을 정하는 데는 충분하고 상위 1비트를 잉여화하여 오류 검출용으로까지 사용할 수 있을 정도이지만, 한글이나 한자 같은 문자를 담는 데는 턱없이 부족하다.

한자는 글자를 체계적으로 부분글자로 분해할 뾰족할 방도가 없는 상태로 글자 수가 너무 많다. 한글은 글자 생성 체계는 한자보다 훨씬 더 유리한 위치에 있지만, 실용적으로 편하게 다루려면 여전히 1만여 개의 미리 조합된 음절 형태를 그대로 배당해야 한다.

예를 들어 현실에서 '학교'라는 단어는 두 글자로 간주되지, 데이터베이스나 문서 분량 같은 데서 5글자라고 계수되는 곳은 아무도 없다. 코드 차지 영역을 줄이자니 메모리 사용량이 늘며, 그리고 오늘날로 치면 화면에 보이는 글자 길이와 메모리를 차지하는 글자 길이가 서로 완전히 따로 노는 complex script 급의 복잡한 기술이 필요해진다.

결국 한글과 한자는 1바이트만으로 표현할 수 없고 통상 2바이트로 표현된다. 그런데 기존 1바이트 영문· 숫자를 건드릴 수는 없으니 1바이트와 2바이트 문자가 공존하는 multi-byte 코드 체계가 만들어진다. 영문권에서 패리티 비트 내지 유럽 특수문자를 표현하는 데 쓰이는 최상위 1비트는, 이 문자가 1바이트로 끝인지 아니면 2바이트 문자의 첫 바이트(lead byte)인지를 판별하는 비트로 쓰인다.
공교롭게도 한글· 한자는 폭도 균일한 2글자 분량을 차지하여 비주얼 상 잘 어울린다. 전각· 반각이라는 개념이 여기서 유래된다.

그런데 lead byte는 그렇다 쳐도 2바이트의 다음 둘째 바이트인 tail byte도 기존 순수 1바이트 문자들과(영문· 숫자 같은) 전혀 겹치지 않게 할 것인지? 아니면 어차피 얘는 lead byte에 의해 변별이 됐으니 좀 문맥 의존적으로 겹치는 걸 허용할 것인지가 문제가 된다. 한글 코드의 경우 완성형은 겹치지 않으나 조합형은 겹친다.

그렇기 때문에 조합형은 tail byte가 대문자 알파벳과 소뭇자 알파벳이 제각기 따로 될 수 있고 심지어 \ 역슬래시 문자가 나올 수도 있다. 이런 이유로 인해 조합형은 1비트 + 초중성 5비트씩 한글의 구성 원리를 매우 잘 반영하여 설계된 문자 코드임에도 불구하고 당시 8.3 제약이 있던 시절에 파일 이름을 사실상 한글로 지정할 수 없었으며, 심지어 이론적으로는 // 주석을 조합형 한글로 지정한 경우 \ 때문에 2-byte aware 하지 않은 컴파일러에서는 충돌이 발생할 수도 있었다.

옛날에 한글 MS-DOS 시절에 한글 도스 셸이나 QBasic처럼 텍스트 GUI(?)를 구현한 프로그램들을 실행해 보면 한국 마소가 굉장히 잘 만든 게 있었다. 메뉴나 대화상자 같은 게 표시되어서 배경에 있던 2바이트 텍스트를 반토막 내더라도 깨진 문자열을 보여주는 법이 결코 없었다. 늘 짝수 바이트가 유지돼야 하는 한글/한자 영역이 홀수 바이트로 줄어들면 가장자리를 하나 삭제해 주면 된다.

그러나 문맥 의존적인 문자 코드로 그런 걸 구현하려면 문자열을 처음부터 읽어 봐야 하고, 두 바이트 중 하나가 소실됐을 때의 뒷처리가 문맥 독립 코드보다 더 어려우면 어렵지 쉽지는 않을 것이다. 불가능하다는 뜻은 아니지만.

조합형을 옹호하고 완성형을 까기에만 바쁜 분들의 심정이야 세벌식+한글 에반젤리스트로서 본인은 적극 이해한다. 그러나 과거의 2바이트 한글 코드의 이면엔 이런 면모도 있었음을 지적하고자 한다. 완성형은 여러 이슈가 얽혀서 그렇게 만들어졌지, 작정하고 한글을 난도질하려는 악의적인 의도로 만들어진 건 아니었다. 문맥 독립성뿐만 아니라 굉장히 보수적인 국제 규격 권장 사항을 만족하는 방식으로 문자 코드를 만들려다 보니, 한글 11172자에다 한자와 각종 특수문자들까지 넣을 절대적인 공간 자체가 부족했기 때문이다.

나중에 완성형에다 어거지로 한글 부족분을 채워 넣은 cp949 확장완성형은 어차피 조합형처럼 문맥 독립성이 깨졌다. 물론, 어차피 이렇게 만들 거면 처음부터 조합형으로 가지 하는 비판은 피할 수 없게 된 게 사실이다. 그런데, 이런 비슷한 삽질을 일본도 문자 코드를 만들면서 했으며, 이를 우리나라도 그대로 답습했을 뿐이다.

조합형과 완성형은 11172자와 2350자의 차이뿐만 아니라 한글 낱자를 표현하는 방식에서 매우 큰 차이가 있다.
조합형은 글자마디와 자모의 차이가 사실상 없다. 그냥 초 중 종성 중 한 성분만 있으면 자모이고, 초성과 중성이 갖춰졌으면 글자마디이다. 초성 ㄱ과 종성 ㄱ을 구분해서 표현할 수 있고 초성+종성이나 중성+종성 같은 '미완성 한글'도 얼마든지 표현할 수 있다.

그러나 완성형엔 그런 개념이 없다. 한글 입력을 처음 시작했을 때 쓰라고 '호환용 한글 자모'라는 게 있는데 그건 한글이 아니라 명목상으로는 '특수문자' 영역이다. 그냥 한글 자모 모양인 그림일 뿐이다. 초성+종성 구분이나 미완성 한글 표현 같은 건 없다.

메모리 1바이트가 아깝던 16비트 도스 시절에 국내에서는 조합형 한글 코드+글꼴이 쓰였지 마소의 윈도처럼 2350자 완성형 코드+글꼴로 돈지랄을 하는 프로그램은 전혀 없었다. 이런 압도적인 인지도의 차이로 인해 조합형은 1992년에 한국의 복수 표준으로 승격되어서 cp1361이라는 이름으로 나름 운영체제의 코드 페이지에 등록도 됐다.

자, 이렇게 컴퓨터는 1바이트 인코딩에다가 한중일 문화권을 위한 1+2바이트 멀티바이트 인코딩 구도가 유지되었고 마소에서는 이를 도스 시절부터 코드 페이지라고 불렀다. 그런데 이런 문자 코드들은 (1) 알파벳· 숫자 같은 공통 문자를 제외하면 같은 문자라 해도 국가마다 배당된 코드값이 같을 수가 없고, (2) 문자 집합 자체의 크기가 너무 작아서 세계 모든 문자들을 한 코드 페이지에다 담을 수 없다는 문제가 있었다.

人(사람 인)이라는 한자가 한국· 중국· 일본의 표준 코드에서의 코드값이 같을 리가 없으니 (1)은 자명한 문제다. (2)의 경우, 2바이트 코드라 해도 앞서 보았듯이 1바이트 문자와의 충돌을 피하기 위해 매우 제한된 영역의 바이트들만 묶을 수 있다. 이 때문에, 문맥 의존까지 시킨다 해도 추가로 만들 수 있는 문자는 1만여 자에 불과하다. CJK에서 쓰는 상용 한자들이나 간신히 다 집어넣을 정도이다.

그래서 1980년대 말부터 이런 발상의 전환이 이뤄졌다. “앞으로 컴퓨터의 메모리는 증가하고 소프트웨어 국제화의 중요성은 커질 테니, 글자 하나의 크기를 16비트로 쿨하게 확장하고 6만여 자의 공간에다가 전세계 언어 문자들을 집어넣고 동일 문자 동일 코드값을 실현하는 게 어떨까?”

이것이 바로 유니코드의 존재 목적 되시겠다. 컴공 전공자가 아니더라도 컴퓨터에서 '유니코드'라는 말은 한 번쯤은 다들 들어 보셨을 것이다. 이건 그야말로 컴퓨터 문자 코드계의 바벨 탑 내지 에스페란토 같은 물건이다.

마이크로소프트는 소프트웨어의 국제화에 굉장한 혜안이 있던 기업이었다. 그래서 OS/2와 결별하고 Windows NT를 첫 개발할 때, 애초부터 8비트 문자가 아니라 유니코드를 담을 수 있는 16비트 문자를 기반으로 설계했다. 심지어는 NTFS 파일 시스템까지도. 그리고는 이를 독자적으로 wide character이라고 부르기 시작했다. 어차피 8비트 문자만으로 충분하던 라틴 문화권에서는 별로 득이 되는 것도 없이 메모리 사용량만 두 배로 뻥튀기되는 대가를 감수하고라도 말이다.

Win32 API는 기존 16비트 윈도 API를 최대한 닮게 설계되었지만, 문자열을 다루는 모든 API에 A 버전과 W 버전 구분이 생겼다. 다만, 32비트 시절에 처음으로 도입된 OLE/COM 같은 기술은 처음부터 오로지 유니코드(= wide) 문자열만 취급하게 만들어졌다.

PE 방식으로 만들어진 32비트 EXE/DLL은 string 테이블, 메뉴, 대화상자 같은 리소스의 저장 포맷도 다 유니코드 방식으로 바뀌었다. 윈도 3.1에다가 Win32s를 설치하면 32비트 커널 DLL뿐만 아니라 각종 코드 페이지 변환 테이블도 설치되는 걸 볼 수 있다. 그게 바로 리소스를 변환하기 위해서이다.

윈도 NT가 3.x나 9x보다 메모리 사용량이 매우 많았던 이유 중 하나도 유니코드 때문이며, 반대로 윈도 9x가 유니코드 API를 지원하지 않았던 이유도 가정용 PC의 부족한 메모리 문제 때문이다.
이 때문에 컴파일 스위치만 바꿔서 유니코드와 기존 멀티바이트를 모두 커버할 수 있는 TCHAR, _T 같은 개념도 그때 생겼다. 두 개의 문자 포맷을 모두 지원하는 작업은 정말 엄청난 대공사였을 것 같다.

Posted by 사무엘

2013/12/13 08:24 2013/12/13 08:24
, , , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/908

16비트 시절에는 잘 알다시피 int 포함 machine word의 크기가 말 그대로 2바이트였다. 그리고 근거리/원거리 포인터가 존재했으며 복잡한 메모리 모델을 따져야 했다. 여기까지는 도스든 윈도든 공통이다. 그럼, 그 시절에 Windows 프로그래밍은 어떠했을까?

16비트 Windows는 잘 알다시피 모든 프로그램이 단일 스레드를 공유하면서 단일 메모리 주소 공간에서 실행되었다. 이런 열악한 환경에서 멀티태스킹을 구현하는 것은 결코 쉬운 일이 아니었다.
그래서 그 시절에는 콜백 함수를 운영체제에다 지정해 주는 것조차도 보통일이 아니었다. 오늘은 오랜만에 이 부분에 대해서 예전에 몰랐다가 최근에 본인이 추가로 알게 된 이야기를 좀 하겠다.

Windows API는 C언어 함수 형태로 만들어졌으니 그때는 지금으로 치면 C++ 가상 함수가 할 일을 함수 포인터로 다 처리하고 있었다. 윈도우 프로시저, 대화상자 프로시저 같은 것 말이다.

그런데 같은 프로그램이 두 번 중첩 실행되면, 코드는 동일하더라도 그 코드가 다루는 스택(데이터) context는 결국 프로세스별로 서로 달라질 수 있게 된다. 이를 어떻게 구분해야 할까?
32비트 이후부터는 가상 메모리 기술이 워낙 발달하여 그 context가 CPU 차원에서 알아서 따로 잘 처리된다. 그러나 16비트 기계엔 그런 개념이 없었다.

결국은, 실제 콜백 함수가 호출되기 전에 그 콜백 함수가 처리할 자신의 데이터 세그먼트 영역을 CPU 레지스터에다 써 주는 stub, 일명 썽킹(thunking) 코드를 소프트웨어적으로 별도로 만들어야 했다. C++로 치면, 클래스 멤버 함수 호출을 위해 this 포인터의 값을 EAX 레지스터에다 써 주는 것과 개념적으로 비슷하다.

우리가 만든 콜백 함수는 그 썽킹 함수를 통해서 호출해야 한 것이다. 운영체제에다가도 당연히 썽킹 함수를 알려 주고 말이다.
이것이 바로 16비트 시절 코드를 보면 밥 먹듯이 보이는 MakeProcInstance와 FreeProcInstance API 함수의 정체이다.
별도의 메모리를 추가로 할당해서 기계어 코드를 추가해 준 것이기 때문에, 메모리의 해제까지 해 줘야 한다.

대화상자 하나를 출력하더라도 아래처럼 말이다.

FARPROC pfnThunkProc = MakeProcInstance( (FARPROC)My_Actual_Dialog_Proc, hInstance); //내 대화상자 프로시저가 우리 인스턴스 핸들을 context로 동작하게 한다
DialogBox(hInstance, "Dialog_Resource_Name", hWndParent, (DLGPROC)pfnThunkProc );
FreeProcInstance(pfnThunkProc);

요즘 같으면 아래의 절차 하나만으로도 충분했을 텐데 말이다.

DialogBox(hInstance, "Dialog_Resource_Name", hWndParent, My_Actual_Dialog_Proc );

결국 My_Actual_Dialog_Proc라는 코드는 시스템 전체를 통틀어서 단 하나 유일하게 존재하겠지만,
이 프로그램을 여러 번 실행하더라도 각 프로그램들은 그 함수로부터 파생된 자신만의 고유한 콜백 함수를 통해서 대화상자를 호출하게 된다.

단, Windows 3.1에서는 함수명을 export해 주는 것만으로 이렇게 콜백 함수에 대한 썽킹을 매번 해 줘야 하는 번거로움을 생략할 수 있었다고 한다.

지금이야 프로그래밍에서 export 키워드라 하면, C++에서 템플릿의 선언과 정의를 번역 단위를 넘나들며 공유할 수 있게 하려 했던 비현실적인 흑역사 키워드일 뿐이다. Windows 플랫폼으로 문맥을 넓힐 경우, export는 클래스나 함수 심벌을 빌드되는 파일 차원에서 외부로 노출하여 GetProcAddress 함수로 노출이 되게 하는 속성 지정자이다. 비주얼 C++ 기준으로 __declspec(dllexport) 라고 쓴다.

지금이야 이런 export 속성은 말 그대로 DLL을 만들 때에나 쓰인다.
그러나 16비트 시절에는 EXE도 운영체제로부터 호출을 받아야 하는 콜백 함수를 넘겨 줄 목적으로 심벌 export를 즐겨 활용했었다.
export된 함수는 외부로부터 호출받는 게 당연시될 거라 여겨졌으므로, 링커와 운영체제가 자체적으로 데이터 세그먼트 보정을 하는 전처리 루틴을 추가해 줬다. 따라서 코드가 훨씬 더 깔끔해진다.

이런 이유로 인해 Windows 3.x 실행 파일들을 헥스 에디터로 들여다보면 대체로 ...WNDPROC, ...DLGPROC 같은 식으로 끝나는 웬 이상한 함수 이름들이 내부에 들어있는 걸 확인할 수 있다. 32비트 이후부터는 찾을 수 없는 관행이다. 자기 내부에서만 쓰는 콜백 함수들을 왜 저렇게 노출해 놓겠는가?

어떤 함수에 export 속성을 부여하기 위해서는 결국 C/C++ 언어에다가 없는 문법을 새로 추가하거나, 아니면 소스 코드는 그대로 놔 두고 컴파일러가 아닌 링커만이 인식하는 부가 정보 같은 게 주어져야 할 것이다. 전자는 소스 코드의 이식성을 떨어뜨린다는 부담이 있지만, 그래도 뒤끝이 없고 한 소스에 빌드에 필요한 모든 정보가 한데 모이니 편리하다. 그래서 그 당시에는 __export라는 비표준 MS 확장 키워드가 도입되었고, 이를 보통 EXPORT라는 매크로로 감싸서 사용하곤 했다. 이런 식으로 말이다.

long FAR PASCAL EXPORT MyWindowProc(HWND hWnd, UINT nMsg, WPARAM wParam, LPARAM lParam); //그 당시 콜백 함수는 반드시 '파스칼' 방식이라는 함수 호출 규약대로 선언되어야만 했다.

한편 후자는 바로 그 이름도 유명한 DEF(모듈 정의) 파일이다.
지금도 DEF 파일이 안 쓰이는 건 아니지만 정말 DLL을 만들 때가 고작이다. 그 반면 16비트 시절에는 DEF가 훨씬 더 중요하게 쓰였던 모양이다.
export하는 콜백 함수뿐만 아니라 이 프로그램에 대한 소개문, 그리고 필요한 스택/힙 크기까지 정확하게 명시되어야 했다.

32비트 이후부터는 스택/힙이 부족하면, 프로그램 로딩 시간이 좀 더 걸릴 뿐이지 실시간으로 추가 할당하여 working set의 확장이 가능한 반면, 16비트 시절에는 메모리 양도 부족하고 또 한 주소 공간에서 여러 프로그램들이 뽁짝뽁짝 복잡하게 지내다 보니 이런 게 핀트가 어긋나면 프로그램 실행이 아예 불가능했을 것 같다.

옛날의 New Executable 포맷에는 자체적으로 name table이라 불리는 범용적인 문자열 테이블이 있었고, import/export하는 심벌 이름은 물론 이 EXE/DLL에 대한 간단한 소개문까지 그런 데에 들어갈 수 있었다.
지금으로 치면 버전 리소스에 들어가는 description과 유사한데 역할 중복인 셈이다. 그런 것까지 DEF 파일에다 명시해 줬었다.

자.. 설명을 들으니 어떤 생각이 드시는지?
16비트 Windows용 실행 파일을 분석하는 도구는 그리 충분치 않다. 일단 개발자들의 친구인 Dependency Walker가 이를 전혀 지원하지 않으며, 그나마 괜찮은 물건으로는 옛날에 Windows 98에 내장되어 있던 QuickView라는 프로그램이 적격이었다. 기본적인 사항은 다 잘 출력해 줬다.

16비트 시절에는 잘 알다시피 HINSTANCE는 각 프로그램의 데이터 세그먼트를 식별하는 번호표에 가까웠고, 개념적으로 지금 같은 포인터가 아니라 오늘날로 치면 오히려 프로세스를 식별하는 HANDLE처럼 널리 쓰였다. (비록 Close를 할 일은 없었겠지만 말이다) 게다가 EXE는 HINSTANCE, DLL은 HMODULE로 성격도 달랐다. 그래서 LoadLibrary 함수의 리턴값은 분명 HMODULE이다.

그때는 EXE/DLL로부터 리소스를 얻어 오는 과정도 정말 복잡했고 Load/Free 절차뿐만 아니라 lock/unlock까지 있었다. 메모리의 절대적인 양이 충분치 않기도 하고 가상 메모리 같은 시스템이 없던 관계로, 단편화를 방지하기 위해 평소에 즉각 쓰지 않는 메모리 블록은 재배치가 가능하게 놔 두는 관행이 더 보편적이었기 때문이다.

한편으로 그때는 시스템 전체에 영향을 끼치기가 쉬웠다. 특히 DLL이 이 분야에 관한 한 지존이었다.
DLL에서 선언한 전역변수는 모든 프로세스가 한데 공유되었으며, DLL이 실행하는 코드는 저런 EXE처럼 여러 컨텍스트에서 중첩 실행될 일이 없고 애초에 데이터 세그먼트 구분을 할 필요가 없었다!

그리고 16비트 시절엔 애초에 콜백 함수를 지정해 주는 과정이 처음부터 저렇게 번거로웠던 만큼, 시스템 전체의 동작 방식을 바꾸는 global 훅을 설치하더라도 훅 프로시저를 반드시 DLL에다가만 만들어야 한다는 제약이 없었다.
그럼에도 불구하고 16비트 시절은 32비트 시절보다 편한 것보다는 불편한게 더 많았다는 것이 부인할 수 없는 사실이다.

끝으로 여담.
이렇듯, 본인은 초등학교 아주 어릴 적부터 프로그래밍을 시작한 관계로, 그 시절에 대한 향수가 있고 '레트로'-_- 컴퓨팅 쪽으로 관심이 많다.
그런데, 그런 것에서조차도 양덕후들의 기상은 갑이다. the old new things 같은 블로그는 이 바닥의 지존이라고 봐야 하고, Windows 3.x로도 모자라서 2.x나 1.x용 프로그램을 만들었다고 인증샷 올리는 사람도 있다.

1985년에 출시된 Windows 1.x의 경우, VGA 카드조차도 없던 시절에 만들어진 관계로 가장 좋은 비디오 모드가 640*350 해상도짜리 EGA이다. 그런데 그걸 640*480 VGA 내지 심지어 800*600 SVGA에서 동작하게 드라이버 패치를 만든 사람도 있다.

참고로 Windows 1.x 정도 되면.. 프로그램 개발을 위한 컴파일러는 그야말로 1986년에 나온 MS C 4.x를 써야 하고, 얘는 함수 호출 인자도 ANSI 스타일이 아니라 K&R 스타일만 써야 하는 진짜 무지막지한 골동품이라고 한다. Windows 1.x는 파스칼로 개발되었다고 들었는데 그래도 그때부터 C 형태의 SDK는 있었던 모양이다.

Posted by 사무엘

2013/11/28 08:29 2013/11/28 08:29
, ,
Response
No Trackback , 2 Comments
RSS :
http://moogi.new21.org/tc/rss/response/903

Windows GUI 프로그램은 잘 알다시피 메시지로 운영체제와 의사소통을 하는 게 핵심이다. “이 창은 응답이 없음. 프로그램을 강제 종료할까요?”라고 판단을 하는 기준은 바로 n초 이상 GetMessage/PeekMessage 함수를 호출하지 않는 프로그램이다.

CreateWindowEx로 창을 하나 만든 뒤 메시지 loop은 GetMessage로 메시지를 받아서 그걸 DispatchMessage로 넘겨 주기를 반복하는 형태이다.
비록 메시지를 윈도우 프로시저로 전달하는 함수로는 CallWindowProc도 있겠지만, Dispatch는 타이머 메시지를 윈도우 프로시저 대신 lParam에 지정된 타이머 프로시저로 직통 전달하는 일까지 한다. 즉, 하는 일의 범위가 더 넓다. 그리고 Call은 메시지 큐를 처리하는 게 아니라 윈도우 프로시저의 서브클래싱용으로 쓰라고 있는 물건이다.

메시지를 Dispatch하기 전에 보통은 translation이라고 불리는 전처리 과정이 필요하다. TranslateMessage 함수가 그 일을 하는데, 키보드 WM_(SYS)KEYDOWN / WM_(SYS)KEYUP 메시지로부터 WM_(SYS)CHAR 메시지를 추가로 생성해 준다. 현재 설정되어 있는 키보드 드라이버의 정보를 토대로 가상 키코드를 해석하여, 그 키가 나타내는 입력 문자를 알려 준다는 뜻이다. 유럽 문자를 입력할 때 쓰이는 dead key를 처리하는 것도 translator의 몫이다.

이때 새로 생성된 메시지는 이 윈도우를 구동하는 스레드의 메시지 큐에 추가로 예약되어서 다음번 GetMessage 함수 호출 때 걸려 나온다. 인자로 전달된 MSG 구조체의 내용이 지금 당장 바뀌지는 않는다. 사실, 문자를 입력받는 윈도우가 아니라면 translation은 꼭 필요하지는 않은지도 모르겠다.

그런데 메시지를 굳이 윈도우 프로시저로 dispatch하기 전에, 응용 프로그램이나 다른 API 함수가 곧장 메시지를 가로채야 하는 경우는 굉장히 많이 있다. 액셀러레이터 단축키를 처리하는 TranslateAccelerator, 그리고 Ctrl+F6 같은 MDI 공용 단축키를 처리하는 TranslateMDISysAccel이 그 예이다.
TranslateMessage는 그런 관문들을 모두 통과한 메시지가 dispatch 직전에 최종적으로 거치는 관문일 뿐이다.

이런 절차가 한둘이 아니기 때문에 MFC의 CWnd 클래스는 그런 코드를 적절히 넣으라고 PreTranslateMessage라는 가상 함수까지 마련해 놓았다. 이 함수에서 키보드 메시지를 조작하여 엔터가 눌려도 대화상자가 종료되지 않게 하는 것 정도는 프로그래밍 초보 시절에 다들 해 보았을 것이다. 그러고 보니 이렇게 dispatch 전단계에서 조작하는 메시지는 다들 키보드 관련 메시지인 경우가 많다.

그리고 이런 식으로 전용 함수를 통해 미리 처리되는 또 다른 대표적인 메시지들은 바로.. 대화상자 관련 메시지들이다.
이걸 담당하는 물건으로는 IsDialogMessage라는 함수가 있다.

물론, MFC의 경우 저 함수를 포함해 위에서 언급한 각종 전처리, translation을 이미 알아서 전부 호출하며 메시지 loop과 심지어 WinMain 함수까지 몽땅 라이브러리 내부에다 짱박아 뒀기 때문에 MFC를 사용하는 프로그램이라면 자신이 직접 그런 함수를 또 호출해야 할 일은 거의 없을 것이다.
그러나 운영체제와 응용 프로그램 사이에 어떤 메커니즘으로 통신이 오가는지 알고는 있을 필요가 있다.

대화상자 안에서 사용자가 tab 키를 눌렀을 때 컨트롤들의 포커스가 바뀌는 것, Alt+알파벳을 눌렀을 때 특정 컨트롤로 바로 이동하는 것, 엔터를 눌렀을 때 '확인' 종료가 되고 ESC를 눌렀을 때 '취소' 종료가 되는 것 따위는 대화상자의 윈도우 프로시저의 관할이 아니다. 윈도우 프로시저가 메시지를 받기 전에 저 IsDialogMessage 함수가 일찌감치 처리한다. 심지어 default 버튼의 테두리를 굵게 칠하는 것조차도 저 함수가 담당한다.
물론 그런 전처리는 대화상자가 독단적으로 하는 게 아니라 자기 아래의 컨트롤에게 WM_GETDLGCODE 메시지를 보내서 컨트롤이 원하는 키보드 처리 양상에 대해서 물어는 보고서 한다.

DialogBox 함수로 modal 대화상자를 만들었다면야 그 함수가 자체적으로 메시지 loop을 돌면서 이런 처리를 모두 알아서 해 준다. 그러나 문제는 modeless 대화상자이다. modeless 대화상자는 그 창을 만든 응용 프로그램의 main 메시지 loop를 같이 쓰면서 돌아가기 때문에 그 loop에서 IsDialogMessage 함수를 호출하는 로직이 추가되어야 한다.

대화상자에서 엔터 키가 들어왔을 때의 동작에 대해서는 살짝 주의할 점이 있다.
일반 버튼은 자체적으로 엔터 키를 처리한다. 그래서 다른 모든 컨트롤들을 사용 중일 때 엔터를 누르면 '확인' 버튼이 눌러진 것으로 처리되고 대화상자가 곧장 종료되지만, '취소'나 '적용' 같은 다른 버튼에 키보드 포커스가 가 있을 때 엔터를 누르면 해당 버튼이 눌러진 것으로 처리된다.

즉, 엔터는 space와 사실상 동일하게 처리된다. 차이가 있다면 space는 key down 시점 때는 버튼이 눌러진 모습만 표시되고 key up 시점일 때 명령이 먹히는 반면, 엔터는 key down 때 곧바로 먹힌다는 것이 전부이다.
다만, 대화상자 안에 또 대화상자가 자식 윈도우로 생성되었고 자식 대화상자 안에 있는 버튼을 space가 아닌 엔터 키로 눌렀을 경우,

WM_COMMAND+BN_CLICKED 메시지는 자식 대화상자의 윈도우 프로시저로 전달되는 게 아니라 겉의 최상위 대화상자의 윈도우 프로시저로 전달된다.
그래서 그 버튼을 엔터 키로 누른 동작은 일반적으로 제대로 인식되지 않거나 최악의 경우 오동작--부모 대화상자와 자식 대화상자에 우연히 ID값이 같은 버튼이 공존한다면!--까지 하게 된다.

왜 그렇게 동작하는지 정확한 이유는 난 모르겠다.
물론, 일반적으로 엔터를 눌러서 대화상자를 닫는 메시지 자체는 자식 대화상자가 아니라 최상위 대화상자에다가 전달되는 게 개념상 올바르다.
하지만 그런 default 버튼이 아니라 일반 버튼을 엔터 키로 누르는 동작까지 왜 엉뚱한 곳으로 가는 걸까?

대화상자 안에 또 대화상자를 만드는 건 운영체제가 제공하는 프로퍼티 시트가 대표적인 예인데 그건 운영체제가 알아서 버튼의 처리를 잘 해 주는 듯하다. <날개셋> 타자연습 같은 프로그램에서 탭 안에 있는 버튼을 엔터로 눌러 보면 잘 안식된다.

그러나 자체적으로 자식 대화상자들을 표시하는 <날개셋> 한글 입력기의 제어판, 그리고 VMware, 반디집, EditPlus 등의 유수의 소프트웨어들이 제공하는 종합 설정 대화상자들을 살펴보면, 자식 대화상자 안의 버튼은 space만 인식되지 엔터 키로 인식되지 않는 걸 알 수 있다. (아래 그림에서 왼쪽)
단, Microsoft Visual Studio는 예외. '도구-옵션' 대화상자의 내부에 표시된 자식 대화상자들의 버튼은 엔터 키로 잘 인식된다. (아래 그림에서 오른쪽) 치명적인 버그 같은 부류는 아니지만 운영체제의 특성 때문에 발생하는 좀 이상한 면모라 하겠다.

사용자 삽입 이미지사용자 삽입 이미지
WM_COMMAND+BN_CLICKED 메시지는 lParam으로 이 메시지를 보낸 컨트롤의 윈도우 핸들을 친절하게 일일이 알려 준다.
그렇기 때문에 그런 버튼을 누르는 걸 인식하려면, 최상위 대화상자의 윈도우 프로시저에서 lParam을 검사하여 이것이 자식 대화상자가 아니라 내 대화상자의 버튼이 보낸 메시지가 맞는지를 확인해야 한다. 아니라면 그 버튼의 진짜 부모 윈도우--GetParent 함수로 확인--에다가 메시지를 도로 보내 버리면 된다.

Visual Studio의 옵션 대화상자도 Spy++로 동작을 확인해 보면, WM_COMMAND+BN_CLICKED 메시지가 두 번 가는 걸 보니 그런 식으로 동작하는 듯하다.

Posted by 사무엘

2013/11/22 08:36 2013/11/22 08:36
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/901

자고로 프로그래밍 언어는 구문이나 예약어 같은 원론적인 것만 정의하는 게 아니라, 그 문법을 토대로 프로그램의 작성에 필요한 각종 기본적인 자료구조와 알고리즘, 입출력 기능들도 라이브러리 형태로 제공한다. 후자의 디자인도 프로그래밍 언어의 정체성에서 차지하는 비중이 매우 크다.

예를 들어 printf, qsort, malloc, fopen 같은 함수를 사용했다면 그 함수들의 몸체도 당연히 프로그램 어딘가에 빌드되어 들어가야 한다. 아니, 애초에 main 함수나 WinMain 함수가 호출되고 각종 인자를 전해 주는 것조차도 그냥 되는 일이 아니다. 이런 것은 C/C++ 언어가 제공하는 런타임 라이브러리가 해 주는 일이며, 우리가 빌드하는 프로그램에 어떤 형태로든 코드가 링크되어 들어간다.

C/C++은 그나마 기계어 코드를 생성하는 언어이기 때문에 그런 런타임의 오버헤드가 작은 편이다. 그러나 비주얼 베이직(닷넷 이전의 클래식)이라든가 델파이는 RAD 툴이고 언어가 직접 GUI까지 다 커버하다 보니 언어가 제공하는 런타임 오버헤드가 크다.
자바나 C#으로 넘어가면 런타임이 단순 코드 오버헤드로 감당 가능한 정도가 아니라 아예 가상 기계 수준이다. 프로그램이 기계어 코드로 번역되지도 않으며, garbage collector까지 있다.

그렇게 프로그래머의 편의를 많이 봐 주는 언어들에 비해 '작은 언어'를 추구하는 C/C++은 도스나 16비트 윈도 시절에는 런타임 라이브러리가 static 링크되는 게 당연시되곤 했다. 오버헤드 자체가 수천~만 몇천 바이트밖에 되지 않을 정도로 매우 작은 편이고, 저수준 언어인 C/C++은 당연히 standalone 바이너리를 만들어야지 무슨 다른 고급 언어처럼 런타임 EXE/DLL에 의존하는 바이너리를 생성한다는 건 좀 안 어울려 보이는 게 사실이었다.

그래서 C/C++로 개발된 EXE 파일은 내부를 들여다보면 대체로, 링크되어 들어간 런타임 라이브러리의 이름과 개발사를 나타내는 문자열이 들어있었다. 볼랜드나 마이크로소프트 따위. 그래서 이 프로그램이 어느 컴파일러로 만들어졌는지를 얼추 짐작도 할 수 있었다.

C 런타임 라이브러리도 static이 아닌 DLL 형태로 제공하려는 발상은 Windows의 경우 아무래도 32비트 NT의 개발과 함께 시작된 듯하다. 그래서 윈도 NT 3.1의 바이너리를 차용해서 개발되었다는 과거의 Win32s를 보면 crtdll.dll이라는 파일이 있는데 이것이 운영체제가 기본 제공하는 프로그램들이 공용하는 C 런타임 DLL인 듯하다. 즉, 메모장, 문서 작성기, 그림판 등의 프로그램들이 호출하는 sprintf 같은 C 함수들의 구현체가 거기에 담겨 있다는 뜻이다.

재미있게도 윈도 NT의 경우, kernel32보다도 먼저 로딩되는 ntdll.dll이 내부적으로 또 각종 C 함수들의 구현체를 제공한다. 커널이 제대로 로딩되기도 전에 실행되는 프로그램이 공유하는 C 함수들이라고 한다.

과거의 윈도 9x의 프로그램들은 비록 32비트이지만 운영체제가 자체적으로 공유하는 C 런타임 DLL은 없다.
다만, 윈도 NT 3.x 이후로 비주얼 C++이 32비트 개발툴로 자리매김하면서 이 개발툴의 버전에 따라 msvcrt20.dll, msvcrt40.dll이 제공되기 시작했고 이들은 윈도 9x에서도 기본 내장되었다. 비록 같은 C 런타임이지만 버전별로 미묘한 차이가 있는 모양이다.

그러다가 1996년에 출시된 비주얼 C++ 4.2부터 C 런타임 DLL은 더 변경을 안 하려는지 파일 이름에서 버전 숫자가 빠지고, 그 이름도 유명한 msvcrt.dll이라는 이름이 정착되어 버전 6까지 쭉 이어졌다.
이 이름은 비주얼 C++ 4.2 ~ 6이 생성한 바이너리가 사용하는 C 런타임인 동시에, NT 계열에서는 기존의 crtdll을 대신하여 운영체제의 기본 제공 프로그램들이 공유하는 C 런타임의 명칭으로도 정착했다.

그리고 9x 계열도 윈도 98부터는 mfc42.dll과 더불어 msvcrt.dll을 기본 제공하기 시작했다.
NT와는 달리 운영체제가 msvcrt.dll을 직접 쓰지는 않지만, 비주얼 C++로 개발된 프로그램들을 바로 실행 가능하게 하기 위해서 편의상 제공한 것이다. 과거의 유물인 msvcrt40.dll은 msvcrt.dll로 곧바로 redirection된다.
그 무렵부터는 오피스, IE 같은 다른 MS 사의 프로그램들도 C 런타임을 msvcrt로 동적 링크하는 것이 관행으로 슬슬 정착해 나갔다.

그렇게 윈도, VC, 오피스가 똑같이 msvcrt를 사용하는 구도가 한동안 이어졌는데..
21세기에 비주얼 C++이 닷넷으로 넘어가면서 그 균형은 다시 깨졌다.
C 런타임 라이브러리도 한 번만 만들고 끝이 아니라 계속 버전업이 되어야 한 관계로 msvcr70, msvcr71 같은 DLL이 계속해서 만들어진 것이다. 결국, 비주얼 C++ 최신 버전으로 개발한 프로그램은 C 라이브러리를 동적 링크할 경우, DLL 파일을 배포해야 하는 문제를 새로 떠안게 되었다.

이것이 비주얼 C++ 2005/2008에서는 더욱 복잡해졌다. C 라이브러리를 side-by-side assembly 방식으로 배포하는 것만 허용했기 때문이다. 쉽게 말해, 레거시 공용 컨트롤과 윈도 XP의 비주얼 스타일이 적용된 공용 컨트롤(comctl32.dll)을 구분할 때 쓰이는 그 기술을 채택했다는 뜻이다.

그래서 msvcr80/msvcr90.dll은 윈도 시스템 디렉터리에만 달랑 넣는다고 프로그램이 실행되지 않는다. 이들 DLL은 DLLMain 함수에서 자신이 로딩된 방식을 체크하여 이상한 점이 있으면 고의로 false를 되돌린다. 그렇기 때문에 이들은 반드시 Visual C++ 재배포 런타임 패키지를 통해 정식으로 설치되어야 한다.

런타임 DLL간의 버전 충돌을 막기 위한 조치라고 하나 이것은 한편으로 너무 불편하고 번거로운 조치였다. C 라이브러리가 좀 업데이트돼 봤자 메이저도 아니고 마이너 버전끼리 뭐가 그렇게 버전 충돌이 있을 거라고..;; 나중에는 여러 프로그램들을 설치하다 보면 같은 비주얼 C++ 2005나 2008끼리도 빌드 넘버가 다른 놈들의 재배포 패키지가 설치된 게 막 난립하는 걸 볼 수 있을 정도였다. 가관이 따로 없다. 당장 내 컴에 있는 것만 해도 2008 기준으로 9.0.32729까지는 똑같은데 마지막 숫자가 4148, 6161, 17, 4974... 무려 네 개나 있다.

개발자들로부터도 불편하다고 원성이 빗발쳤다. MS Office나 Visual Studio급으로 수십 개의 모듈로 개발된 초대형 소프트웨어를 개발하는 게 아니라면, 꼬우면 그냥 C 라이브러리를 static 링크해서 쓰라는 소리다.
그래서 비주얼 C++ 2010부터는 C 라이브러리 DLL은 다시 윈도 시스템 디렉터리에다가만 달랑 집어넣는 형태로 되돌아갔다. 다시 옛날의 msvcrt20, msvrt40, msvcr71처럼 됐다는 뜻이다.

윈도 비스타 타임라인부터는 운영체제, VC, 오피스 사이의 관계가 뭔가 규칙성이 있게 바뀌었다.
오피스는 언제나 최신 비주얼 C++ 컴파일러가 제공하는 C 라이브러리 DLL을 사용하며, 운영체제가 사용하는 msvcrt도 이름만 그럴 뿐 사실상 직전의 최신 비주얼 C++가 사용하던 C 라이브러리 DLL과 거의 같다.

그래서 오피스 2007은 msvcr80을 사용하며, 오피스 2010은 비주얼 C++ 2008에 맞춰진 msvcr90을 사용한다. C 런타임 DLL도 꾸준히 버전업되고 바뀌는 물건이라는 것을 드디어 의식한 것이다. 비스타 이전에 윈도 2000/XP의 EXE/DLL들은 헤더에 기록된 링커 버전을 보면, 서로 사용하는 컴파일러가 다르기라도 했는지 통상적인 비주얼 C++이 생성하는 EXE/DLL에 기록되는 버전과 일치하지 않았었다. 9x는 더 말할 필요도 없고.

그럼에도 불구하고 msvcrt는 운영체제 내부 내지 디바이스 드라이버만이 사용하고, 비주얼 C++로 개발된 여타 응용 프로그램들은 언제나 msvcr##을 사용하게 용도가 확실하게 이원화되었다.
그래서 심지어는 똑같이 MS에서 개발한 한글 IME임에도 불구하고 Windows\IME 디렉터리에 있는 운영체제 보급용은 msvcrt를 사용하고, 한글 MS Office가 공급하는 IME는 Program Files에 있고 msvcr##을 사용한다. 둘은 거의 똑같은 프로그램인데도 말이다.

이것이 Windows와 C 런타임 라이브러리 DLL에 얽힌 복잡한 역사이다. 여담이지만 C 라이브러리 중에서 VC++ 2003이 제공한 msvcr71은 Windows 95를 지원한 마지막 버전이다. 2005가 제공한 msvcr80부터는 일부 보안 관련 코드에서 IsDebuggerPresent라는 API 함수를 곧장 사용함으로써 Windows 95에 대한 지원을 중단하였으며, 최하 98은 돼야 동작한다. VC++ 2008부터는 9x 계열에 대한 지원 자체가 중단됐고 말이다.

자, 여기서 질문이 생긴다. 그럼 C++은 사정이 어떠할까?

C보다 생산성이 훨씬 더 뛰어난 C++로 주류 프로그래밍 언어가 바뀌면서 표준 C++ 라이브러리에 대한 동적 링크의 필요성도 응당 제기되었다. 그러나 이것은 C 라이브러리보다는 시기적으로 훨씬 더 늦게 진행되었기 때문에 가장 먼저 등장하는 비주얼 C++의 DLL 이름이 msvcp50과 msvcp60이다. 즉, 비주얼 C++ 5.0 이전에는 선택의 여지 없이 static 링크만 있었다는 뜻이다.

더구나 이것은 전적으로 비주얼 C++ 소속이지, 운영체제가 따로 C++ 라이브러리 DLL을 제공하지는 않는다. MS에서 만들어진 제품들 중에 msvcp##를 사용하는 물건은 비주얼 C++ IDE와 컴파일러 그 자신밖에 없다.

C++ 라이브러리는 대부분 템플릿 형태이기 때문에 알고리즘 뼈대는 내 바이너리에 static 링크되는 게 사실이다. 그러나 그렇게 덧붙여지는 라이브러리 코드가 별도로 호출하는 함수 중에 DLL에 의존도를 지니는 게 있다. cout 객체 하나만 사용해도, 그리고 STL 컨테이너 하나만 사용한 뒤 빌드해 봐도 형체를 알 수 없는 이상한 메모리 관리 쪽 함수에 대한 의존도가 생긴다.

그래도 C 라이브러리 DLL은 사용한 함수에 따라서 printf, qsort 등 링크되는 심벌이 명확한 반면
C++ 라이브러리는 내부 구조는 이거 뭐 전적으로 컴파일러가 정하기 나름이고 외부에서 이들 심벌을 불러다 쓰기란 사실상 불가능하다는 큰 차이가 있다.

<날개셋> 한글 입력기는 C++ 라이브러리를 사용하지 않으며, 빌드 후에 생성된 바이너리를 인위로 수정하여 msvcr## 대신 강제로 운영체제의 msvcrt를 사용해서 동작하게 만들어져 있다.

Posted by 사무엘

2013/11/19 08:29 2013/11/19 08:29
, , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/900

지뢰찾기 연구

요즘 팔자에도 없던 지뢰찾기에 살짝 재미가 붙었다.
본인은 비슷한 학력· 경력으로 IT 업계에 종사하는 여느 사람들과는 달리, 머리 싸움을 즐기는 스타일이 전혀 아니었으며 복잡한 퍼즐 게임 따위와도 담을 쌓고 지내는 편이었다. 이런 점에서 본인은 완전 퍼즐 게임 매니아인 T모 님과는 성향이 다르다.

그래도 지뢰찾기 정도면 요령을 알고 나니까 은근히 재미있다. 초보 레벨로는(9*9, 지뢰 10개) 40초~1분 남짓한 시간 동안 대략 60~70%대의 승률로 깨겠다. 처음엔 초보 레벨조차도 5분이 넘게 끙끙대기도 했으나, 마치 경부선 서울-부산 열차의 운행 시간이 17시간에서 6시간대~4시간대로 줄어들듯이 시간이 단축되었다.

사용자 삽입 이미지
지뢰찾기는 소련에서 개발된 테트리스와 더불어 시간 죽이기용으로 상당히 적절한 컴퓨터용 퍼즐인 거 같다. 여느 보드 게임과는 달리, 물건이 먼저 존재하다가 컴퓨터로 옮겨진 게 아니라 처음부터 컴퓨터용으로 만들어진 게임이라는 차이가 있다.

맥북의 터치패드 격인 트랙패드로는 도저히 게임을 할 수 없는 듯했다.
두 손가락을 동시에 누르거나 패드 우측 하단을 지그시 누르면 우클릭이 되긴 하는데, 이게 생각보다 정확하게 인식되지가 않는 듯하기 때문이었다.

지뢰가 있다는 깃발만 꽂으려고 우클릭을 했는데, 그게 좌클릭으로 인식되어 지뢰를 밟고 장렬히 죽는 참사가 한두 번 발생하는 게 아니어서 말이다. 단, Windows Vista 이후부터 새로 개발된 지뢰찾기는 Shift+클릭으로 우클릭, 더블클릭으로 좌우 클릭도 돼서 조작이 훨씬 더 편해졌다.

키보드로는 Space는 셀 개봉(좌클릭)이고, Shift+Space가 깃발(우클릭)이다.
그런데 이번엔 깃발이 꽂힌 것을 제외한 모든 인접 셀들을 한꺼번에 개봉하는 건 키보드로 어떻게 하는지 모르겠다. 게임에 익숙해지고 나면 셀 개봉은 하나씩 클릭하는 것보다 저렇게 개봉을 훨씬 더 즐겨 하게 되는데 말이다.

지뢰찾기라는 게임은 풀이 순서를 논리적으로 명확하게 유추 가능한 상황이 대부분이지만, 가끔은 주어진 정보만으로는 정확한 지뢰 배치를 알 수 없어서 찍기(guessing)를 해야 하는 경우도 있다. 지뢰가 정확하게 어떤 조건으로 배치되어 있을 때 그런 상황이 생기는지는 잘 모르겠다.

숫자 정보로부터 유추 가능한 지뢰 배치 가짓수는 기본적으로 폭발적으로 증가할 수 있으며, 어떻게 될 수 있는지 백트래킹으로 일일이 하나하나 때려박아 넣으며 추적을 하는 수밖에 없다. 뭔가 네모네모 로직을 푸는 것 같은 느낌이 들기도 한다. 이 때문인지 이 문제는 전산학적으로 봤을 때 NP 완전 문제라는 것까지 증명되었다.

그리고 찍기가 필요 없는 명확한 상황일 때 사람이 지뢰를 찾는 절차는 의외로 아주 명료하고 기계적이다.
딱 이 정도 영역이 개봉되고 인접 셀의 지뢰 정보가 이렇게 주어졌을 때, '명백한 해법' 하나만 동원해서라도 컴퓨터가 게임 진행을 충분히 도와 줄 수 있겠다는 생각이 들었다.

그래서, 막간을 이용해 지뢰찾기를 푸는 프로그램을 짜 봤다.
초-중급 수준의 간단한 클래스 설계와 알고리즘 구현이 동원되니 심심풀이 땅콩 코딩용으로 꽤 적절한 거 같다!
'명백한 해법'을 적용할 수 없어서 '찍기'를 해야 할 때, 지뢰가 있을 만한 위치를 가장 유력하게 유추하는 것 정도까지 구현해야 비로소 중급-고급 사이를 넘볼 수 있지 싶다.

대략의 코딩 내역은 이러하다.
지뢰 답을 알고 있는 MineSource 클래스(각 칸마다 지뢰 여부를 실제로 담고 있는 2차원 배열),
그리고 그 MineSource에다가 쿼리를 해 가며 1~8 숫자와 자기가 찾아낸 지뢰 위치 정보만을 알고 있는 MineSolver 클래스를 만들었다.
이들은 다 2차원 배열과 배열의 크기는 공통 정보로 갖고 있으므로 MapData라는 동일 기반 클래스를 설정했다.

MineSource는 특정 위치 x,y에 대한 쿼리가 온 경우, MineSolver에다가 인접 셀들의 지뢰 개수를 써 준다. 인접 셀에 지뢰가 하나도 없다면 여느 지뢰찾기 프로그램이 그러는 것처럼 인접 셀 8개도 한꺼번에 개봉하면서 flood fill을 한다.
곧바로 지뢰를 찍었다면 당연히 곧바로 게임 오버라고 알려 준다. 그리고 요즘 지뢰찾기 게임 구현체들이 그런 것처럼, 첫 턴에서는 절대로 지뢰를 찍는 일이 없게 내부 보정을 하는 것도 이 클래스에서 하는 일이다.

지뢰찾기의 '명백한 해법'은 딱 두 가지이다.

  1. 열리지 않은(지뢰 마크가 있는 놈 포함) 인접 셀의 개수와 자기 숫자가 '같은' 셀은 주변 미개봉 셀이 다 지뢰임이 100% 확실하므로 그것들을 전부 지뢰 마크(깃발)로 표시한다.
  2. 깃발이 꽂힌 주변 셀의 개수와 자기 숫자가 같은 셀의 경우, 지뢰 마크가 없는 나머지 열리지 않은 인접 셀은 지뢰가 아닌 게 100% 확실하다. 따라서 전부 개봉한다.
  3. (위의 명백한 해법만으로 개봉할 만한 셀이 존재하지 않는 건 운이 나쁜 케이스다. 패턴을 기반으로 랜덤 추측을 해야 하는데, 이건 일단 보류.)

텍스트 모드에서 자기 스스로 무작위하게 지뢰밭을 만들고 지뢰찾기를 풀기도 하는 자문자답 프로그램을 만드니, 200줄이 좀 안 되는 코드가 완성되었다.
이 프로그램은 인접 셀에 대해서 뭔가 조건을 만족하는 셀의 개수를 세거나, (getCount) 일괄적으로 동일한 조치를 취하는(doAction) 패턴이 많다.

이걸 그냥 for(j=y-1; j<=y+1; j++) for(i=x-1; i<=x+1; i++)이라는 2중 for문만으로 돌리기에는 i나 j가 boundary 밖인 경우도 고려해야 하고, (i,j)가 (x,y)와 같은 위치인 경우도 피해 가야 하기 때문에 loop 자체가 생각보다 복잡하다.
그러니, 그 loop 자체만 하나만 짜 놓고 loop 안에서 하는 일을 그때 그때 달리 지정하는 것은 템플릿-람다로 깔끔하게 설계했다.

다음은 프로그램의 간단한 실행 결과이다.

after the first turn:
+ + 1 . . . . . .
+ + 1 . 1 1 1 . .
+ + 1 . 1 + 2 1 .
+ + 1 . 1 2 + 1 .
1 1 1 . . 1 + 2 1
. . . . 1 1 + + +
. . . . 1 + + + +
. 1 1 2 2 + + + +
. 1 + + + + + + +

(중간 과정 생략)

picking 7 9
@ @ 1 . . . . . .
2 2 1 . 1 1 1 . .
1 1 1 . 1 @ 2 1 .
1 @ 1 . 1 2 @ 1 .
1 1 1 . . 1 2 2 1
. . . . 1 1 3 @ 2
. . . . 1 @ 3 @ 2
. 1 1 2 2 2 2 1 1
. 1 @ 2 @ 1 . . .
You Won!


이 정도 초보적인 지뢰 찾기 풀이 프로그램은 이미 다 개발되고도 남았으니,
유튜브를 뒤지면 신의 경지 수준의 속도를 자랑하는 지뢰찾기 TAS (매크로 프로그램 내지 역공학을 동원한 게임 스피드런) 동영상들이 나돌고 있다.

여담이다만, 지뢰찾기를 하다가 지뢰를 밟아서 게임 오버가 될 때 본인은 깜짝 깜짝 잘 놀란다. =_= 마치 옛날에 페르시아의 왕자를 하는데 타이밍을 잘못 잡아서 왕자가 쇠톱날(chopper)에 두 동강 나서 죽는 것 같은 그런 느낌이다.

Posted by 사무엘

2013/09/26 08:32 2013/09/26 08:32
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/881

간단한 인트린직 이야기

요즘 컴파일러에는 인트린직(intrinsic)이라고 정의된 내장 함수들의 집합이 있다. 그래서 그런 함수를 호출한 것은 실제 함수 호출이 아니라 특정 기계어 코드로 곧장 치환된다. 함수의 몸체가 직접 삽입된다는 점에서는 함수 인라이닝과 비슷하지만, 인트린직은 그 몸체가 컴파일러에 의해 내장되어 있으니 개념과 용도가 그것과는 살짝 다르다.

인트린직은 굳이 인라인 어셈블리 같은 거창한 문법 없이 간단한 C 함수 호출 스타일로 특정 기계어 인스트럭션을 곧장 집어넣거나 컴파일러의 확장 기능을 사용하기 위한 목적이 강하다. #pragma가 특수한 의미를 지닌 지시를 내리기만 하는 전처리기로 비실행문이라면, 인트린직은 실행문이다.

또한, 기존의 표준 C 함수가 인트린직 형태로 몰래 처리되기도 한다. memset, strcpy처럼 간단한 메모리 조작은 컴파일러가 아예 직통 대입 코드를 집어넣는 식으로 최적화를 하기도 하며, 각종 수학 함수들도 FPU 명령 하나로 곧장 치환되는 게 보통이다. 가령 제곱근을 구하는 sqrt함수는 곧바로 fsqrt 인스트럭션으로 말이다.

C 라이브러리 DLL인 msvcr*.dll은 여전히 수학 함수 심벌들을 제공한다. 그러나 요즘 컴파일러가 수학 연산을 인트린직 대신 일일이 그런 함수 호출 형태로 곧이곧대로 사용하는 경우란, 수학 함수들을 함수 포인터 형태로 접근해야 할 때밖에 없다.

비주얼 C++이 제공하는 여러 인트린직 함수 중에는 '일을 하지 않음'(no operation)을 의미하는 __noop이라는 함수가 있다. x86의 nop 인스트럭션(코드 바이트 0x90)과 비슷한 발상인데, nop를 생성하기라도 하는 것도 아니다. 컴파일러는 파싱만 해 주지 코드 생성은 안 하고 넘긴다. 파이썬으로 치면 pass와 비슷한 물건이다.

파이썬은 세미콜론 같은 구분자도 없고 공백 들여쓰기가 유효한 의미를 갖기 때문에 empty statement를 표현하려면 pass 같은 별도의 문법이 반드시 필요하다. 그러나 C/C++은 ; 하나만 찍어 줌으로써 empty statement쯤이야 얼마든지 만들 수 있는데 굳이 저런 잉여로운 인트린직은 왜 필요한 걸까?

__noop의 주 용도는, 가변 인자를 받는 디버그 로그를 찍는 함수의 컴파일 여부를 제어하는 것이다.

#ifdef _DEBUG
    #define WRITE_LOG   WriteLog
#else
    #define WRITE_LOG   __noop
#endif

WRITE_LOG("Start operation");
WRITE_LOG("Operation ended with code %d", nErrorCode);

함수가 가변 인자가 아니라면, WRITE_LOG 자체를 매크로 상수가 아닌 매크로 함수로 선언하면 된다.

#ifdef _DEBUG
    #define WRITE_LOG1(msg,a1)  WriteLog(msg,a1)
#else
    #define WRITE_LOG1(msg,a1)  0
#endif

이렇게 해 주면 디버그가 아닌 릴리즈 빌드에서는 WriteLog가 호출되지 않을 뿐더러, 매개변수들의 값 평가도 전혀 발생하지 않게 된다.
그러나 매크로 함수는 가변 인자를 받을 수 없기 때문에 임의의 개수의 인자를 모두 커버하려면 결국 함수 이름 자체만 치환하는 매크로 상수를 써야 한다. 매크로 상수는 함수의 호출만 없앨 수 있지 함수로 전달되는 매개변수들의 값 평가를 없앨 수는 없다. 뭐, 상수들의 나열이야 컴파일러의 최적화 과정에서 제거되겠지만 side effect가 남는 함수 호출은 어떡하고 말이다.

이런 이유로 인해 가변인자를 받는 디버그 함수를 제어하는 매크로는 범용적인 버전뿐만 아니라 매개변수 고정 버전도 같이 딸려 나오는 게 관행이었다. 대표적인 게 MFC의 TRACE 매크로이다. TRACE0~TRACE3도 있다. 한번 함수를 호출할 때 전달되는 매개변수의 개수가 런타임 때 매번 바뀌는 것도 아니니, 가능하면 고정 버전을 쓰는 게 프로그래밍 언어의 관점에서 더 안전했기 때문이다.

그런데 비주얼 C++의 __noop은, 하는 일은 없으면서 0개부터 n개까지 아무 개수로 그 어떤 type의 인자를 넘겨줘도 되는 훌륭한 페이크 함수이다. 그래서 매크로 상수를 이용해서 그 어떤 함수도 __noop로 치환하면 그 함수의 호출은 깔끔하게 무시되고 코드가 생성되지 않는다.

게다가 코드는 생성되지 않지만 컴파일러가 각 토큰에 대한 구문 분석은 해 준다는 점에서 __noop은 매크로 상수뿐만 아니라 매크로 함수보다도 더 우월하다.
WRITE_LOG1에다가 아예 얼토당토 않은 선언되지 않은 변수를 집어넣을 경우, 이것을 그냥 0으로만 치환해 버리는 코드는 디버그 버전에서만 에러가 발생하고 릴리즈 버전은 그냥 넘어간다.

그러나 __noop으로 치환하면 효과는 0 치환과 동일하면서 릴리즈 버전에서도 컴파일 에러가 뜬다. 그러니 더욱 좋다.
이 인트린직은 #pragma once만큼이나, 그야말로 기존 C/C++ 문법만으로는 뭔가 2% 부족한 면모가 있는 걸 채워 준 물건이 아닐 수 없다. 컴파일러 개발사들이 괜히 비표준 꼼수를 집어넣는 게 아니다. 그 꼼수가 정말 타당하다고 여겨지면 다음 표준 때 정식으로 반영까지 될 테고.

아무 일도 안 하는 null instruction은 코드 바이트도 0으로 하는 게 직관적이지 않나 싶은데..
아까도 얘기했듯이 x86은 의도적으로 쉽게 떠오르지 않는 값에다 그 명령을 할당했다.
크기 최적화를 하지 않고 프로그램을 빌드하는 경우(디버그 또는 속도 최적화), 비주얼 C++은 machine word align을 맞추거나 edit and continue용 공간을 확보해 두기 위해 코드 바이트를 약간 듬성듬성하게 배치하는데, 과거의 6.0은 그 빈 틈에 nop(0x90)를 집어넣었다.

그러나 언제부턴가 닷넷부터는 그 버퍼 코드가 int 3(0xCC)으로 바뀌었다.
정상적인 경우라면 거기는 도달해서는 안 되는 곳인데, 그냥 아무 일 없이 nop로 넘어가는 게 아니라 breakpoint가 걸리게 보안을 강화한 게 아닌가 싶다.

말이 나왔으니 말인데, int 3을 집어넣어 주는 인트린직도 응당 존재한다. 바로 __debugbreak 함수이다. 이건 사실 Windows API에도 DebugBreak()로 있기도 하고 말이다.
이걸 쓰면 비주얼 C++ IDE에서 F9를 누른 것과 동일한 효과를 낼 수 있다. 디버거를 붙여서 실행할 경우, 그 지점에서 프로그램의 실행이 멈춘다.

Posted by 사무엘

2013/09/20 08:30 2013/09/20 08:30
, , , ,
Response
No Trackback , 2 Comments
RSS :
http://moogi.new21.org/tc/rss/response/879

지금으로부터 수십 년 전에는 동네마다 컴퓨터 학원이 있었고, 꼬꼬마가 프로그래밍을 공부하겠다고 하면 으레 GWBASIC부터 시작하곤 했다. 베이직은 16비트 MS-DOS뿐만 아니라 각종 가정용 8비트 컴퓨터에도 특유의 인터프리터 환경이 내장되어 있기도 해서 접하기가 한결 쉬웠다.

그때와는 달리 오늘날의 컴퓨터 교육은 이미 만들어진 소프트웨어들을 활용만 하는 실무에만 치우친 편이다.
지금 컴퓨터 프로그래밍을 처음부터 공부하고 싶다면 무엇부터 시작하는 게 좋을까?
이 질문에 대한 답변은 그 사람이 무슨 프로그램을 작성하고 컴퓨터로 무엇을 하고 싶은지 목적에 따라 크게 달라진다.
이 글은 나의 지극히 좁은 편견만을 반영하고 있으므로, 당연히 프로그래머마다 생각이나 견해가 다를 수 있다.

1. 비전문가/비전공자로서 그냥 최소한의 시간 투자로 개인적인 컴퓨터 활용도만 높이고 싶다면(고급 계산기 + 기초 알고리즘 실습 + 파일 자동 조작 + 매크로/자동화 도구 등)

개인적으로 파이썬을 추천한다. 복잡한 자료형을 다루기가 쉬워서 여타 언어들에 비해 짧은 코드만으로 복잡한 일을 한번에 끝낼 수 있다. 방대한 크기의 파일을 읽어서 내가 원하는 처리를 한 뒤 출력을 뱉어내는 수십 줄 남짓한 프로그램만 짤 줄 알아도 인생이 굉장히 편해질 수 있다.
좀 수학 덕후 기질이 있다면, 함수형 프로그래밍 언어를 건드려 봐도 될 듯.

2. 1보다는 좀 더 나아가서 가성비가 뛰어난 개발 환경에서 최소한의 GUI까지라도 만들어 보고 싶으면

Windows 플랫폼 한정으로 C#급 언어가 가장 좋겠다.

3. 웹브라우저에서 어지간한 애니메이션이나 프레젠테이션을 다 띄우고, 글이나 그림을 계산 결과로서 출력하고 싶으면

HTML + 자바스크립트.
요즘은 HTML이 단순히 화면에 뿌려지는 글과 그림, 하이퍼텍스트 문서일 뿐이라고 생각하는 건 큰 오산이다.
문서에다 서식을 주는 건 이제 CSS라는 방대한 별도의 규격으로 독립해 나가고, HTML은 문서 반 코드 반이다. 실시간으로 내용이 업데이트되고 화면 끝까지 스크롤됐을 때 추가로 컨텐츠를 로딩하고.. 사용자의 조작에 반응하여 그림을 뿌려 주는 등, 예전에는 ActiveX나 하다못해 플래시라도 써야 했을 컨텐츠들이 지금은 저것만으로 다 된다.

웹브라우저가 거의 플랫폼 독립적인 프로그램 구동 플랫폼처럼 바뀌었으니, 이를 활용할 줄 알면 역시 컴퓨터 활용 능력이 크게 향상될 수 있다. 웹 프로그램은 다른 언어나 런타임, IDE 같은 걸 설치할 필요조차 없이, 그냥 메모장에서 코딩 후 웹브라우저에서 곧바로 돌려보면 된다.

4. 맥 OS용 응용 프로그램이나 아이폰 앱을 개발하고 싶다면

Objective C + xcode + COCOA API 등등으로 고고씽이다. 일단 맥북을 장만해야 할 것이고 Windows와는 너무 이질적인 개발 환경 때문에 처음에 고생 많이 할 것이다.

5. 안드로이드 스마트폰용 앱을 개발하고 싶다면

자바 + 이클립스 IDE에 익숙해져야 할 것이다. Java는 요즘 스마트폰 앱 개발용 언어로 입지가 확 되살아난 듯하다. 이게 완전한 웹용 언어도 아니고(자바스크립트는 자바와 전혀 다른 언어임), 자바 애플릿이 플래시/ActiveX를 완전히 대체하는 RIA (rich internet application) 프레임워크로 자리잡은 것도 아니고, 로컬에서는 느리고 성능이 안 좋다 보니 전통적인 기계어 프로그램들에 밀려서.. 예전까지는 위상이 좀 어정쩡했기 때문이다. 로컬에서는 일부 크로스플랫폼 소프트웨어의 GUI(프런트 엔드)를 돌릴 때나 좀 쓰이곤 했다.

6. 끝으로, PC + Windows 환경에서 네이티브 코드 + standalone으로 실행되는 프로그램을 개발하고 싶다면

아래아한글이나 <날개셋> 한글 입력기나 어지간한 온라인 게임과 같은 급의 기계어 실행 파일을 만들고 싶다면..
역시나 재래식 Visual C++이나 최소한 델파이 같은 툴로 가야 한다.
개발 환경, 언어 문법과 기본 라이브러리, Windows API, 그 뒤 개발 분야에 따라 추가적인 라이브러리 공부까지 산 넘어 산이다.

오늘날 프로그램 개발 환경이 결국 로컬 + 웹 + 앱이라는 세 양상으로 구분된다고 예전에 글을 쓴 적이 있는데.. 그것과도 관계가 있다.
프로그래밍, 더 나아가 소프트웨어 개발에 관심이 있는 분이라면 이런 아이템들을 참고하면 되겠다.
그런데 정작 이런 글을 쓴 본인은 6만 빼고 나머지 분야는 여전히 너무 모른다는 게 함정..ㅎㅎ

Posted by 사무엘

2013/09/17 08:37 2013/09/17 08:37
,
Response
No Trackback , 13 Comments
RSS :
http://moogi.new21.org/tc/rss/response/878

1. 클립보드 개론

과거에 Windows 3.x 시절에는 '클립보드 표시기'(clipbrd.exe)라는 프로그램이 있었다. 95/98 시절에도 있다가(16비트 바이너리 형태 그대로) 운영체제가 NT 계열로 바뀌면서 완전히 역사 속으로 사라진 듯하다.
그러나 지금도 그런 부류의 액세서리 프로그램이 있으면 좋겠다는 생각을 개인적으로 가끔은 한다. 번거롭게 여타 프로그램을 띄워서 '붙이기' 명령을 내리지 않고도 클립보드에 지금 무엇이 들어있는지를 확인할 수 있기 때문이다.

사실, 제3자가 개발한 클립보드 표시/관리 유틸리티는 당연히 존재한다. 이런 프로그램은 단순히 클립보드 표시 기능뿐만 아니라 클립보드 내용을 파일로 저장하거나 불러올 수도 있고, 지금 MS Office 프로그램들이 그러는 것처럼 여러 개의 클립보드 데이터를 관리하는 기능도 있어서 잘만 활용하면 대단히 편리하다.

기술적으로 봤을 때 클립보드는 여러 프로그램들이 한데 공유할 수 있는 메모리 핸들의 집합이다.
0과 1의 나열일 뿐인 데이터가 텍스트인지 이미지인지 포맷을 식별하는 정수값이 있고, 그 포맷 식별자와 메모리 핸들이 한데 대응하여 튜플을 이룬다.

클립보드에는 여러 종류의 데이터가 동시에 공존할 수 있다. 그래서 워드 프로세서라면 자신만의 고유한 포맷을 등록해서 자신이 만든 모든 정보가 완전히 보존되어 있는 데이터를 놔 둬야겠지만(예를 들어, 이 데이터가 일반 블록이 아니라 칼럼 블록이라는 표시도..), 같은 데이터에 대해서 메모장 같은 프로그램에서도 최소한 텍스트라도 붙여 넣을 수 있게 표준 텍스트 포맷으로도 데이터를 보관해 줘야 한다.

클립보드로부터 데이터를 가져오거나, 거기에다 내 데이터를 저장하려면 먼저 OpenClipbaord 함수를 호출해서 클립보드를 열면 된다. 이 함수가 왜 윈도우 핸들(HWND)을 인자로 받는지는 잘 모르겠다. 클립보드의 사용이 끝난 뒤엔 CloseClipboard를 하면 된다.

클립보드 API는 한 순간에 시스템 전체를 통틀어 단 한 프로그램/스레드만 클립보드에 접근하는 걸 가정하고 만들어졌다. 그래서 딱히 OpenClipboard 함수가 무슨 다른 핸들 같은 걸 되돌리지는 않는다.

2. 클립보드를 위한 메모리 할당 함수

클립보드에다 데이터를 지정하거나 가져오는 건 Set/GetClipboardData 함수로 하면 된다. 이때 주고받는 핸들은 GlobalAlloc 함수를 이용하여 특수하게 할당된 메모리이다.
클립보드 API는 구시대 16비트 Windows 시절의 디자인을 그대로 답습하고 있는 게 많다. 클립보드는 지금 같은 memory mapped file이나 가상 메모리 같은 게 없던 시절부터 존재했다. 그때는 운영체제에 global heap과 local heap이라는 두 종류의 메모리가 존재했고, 클립보드는 응당 global heap의 영역에 존재했다.

운영체제의 heap 함수는 고정된 메모리 주소에다 공간을 바로 할당시킬 수도 있고, 할당은 하되 당장 그 메모리를 사용하지 않을 경우 실제 위치를 운영체제가 재량껏 재배치도 하다가 응용 프로그램이 실제로 잠깐 사용을 할 때만 메모리를 고정시키는 '유동적인' 방식으로 할당할 수도 있다.

메모리를 사용하는 프로그래머의 입장에서는 무척 번거로운 일이지만, 당장 사용하지 않는 메모리를 운영체제가 필요에 따라 재배치 가능하게 할당해 놓으면, 아무래도 PC의 절대적인 메모리 공간이 충분치 않을 때 메모리의 단편화를 예방할 수 있어서 효율적이다. API 자체가 그렇게 헝그리 정신과 상호 협력 이념을 염두에 두고 설계돼 있다는 뜻이다.

GlobalAlloc 함수에는 메모리를 할당할 때 클립보드/OLE 공유가 가능하게 하는 GMEM_DDESHARE 같은 여러 플래그를 줄 수 있다. 이게 어찌 보면 16비트 시절의 VirtualAlloc 함수 같기도 하다. 하지만 32비트로 오면서 GlobalAlloc 함수의 잡다한 플래그들은 다 legacy 잉여로 전락했고, 메모리를 유동적으로 할당할지/고정적으로 할당할지, 그리고 할당된 메모리를 0으로 초기화도 할지를 설정하는 플래그만이 현재 유효하다.

이 함수는 이제 클립보드 복사나 OLE drag & drop 기능을 구현할 때밖에 쓸 일이 없다. 아니면 아주 특수한 상황에서 프로세스의 기본 heap에 의존하지 않고 메모리를 할당할 일이 있을 때나 쓰든가.
32비트 이후부터는 global heap과 local heap의 구분도 없고, 또 이 함수로 개당 몇십 바이트짜리 연결 리스트의 노드를 일일이 저장한다거나 하는 건 바보짓이다.

3. 클립보드 표시기 만들기

일반적으로는 클립보드에 접근해서 데이터를 읽고 쓰고, 클립보드를 비우는 것만 알면 된다.
그것보다 조금 더 고급으로 나가면 나만의 클립보드 포맷을 등록하고 다양한 클립보드 포맷을 조회하는 조작까지 필요해진다.
그 다음으로 클립보드와 관련된 가장 복잡한 조작은 바로, 클립보드 내용이 바뀌었을 때 통지를 실시간으로 받겠다고 운영체제에다 요청하고 실제로 그런 일이 일어났을 때 각종 뒷처리를 하는 일이다.

이렇게 클립보드의 변경 내역을 통지받는 프로그램을 개념적으로 '클립보드 표시기(viewer)'라고 부른다. 모든 프로그램들이 사용자가 누르는 Ctrl+C/X에 관심이 있는 게 아니니, 클립보드 변경 내역은 특별히 요청을 한 프로그램에게만 알려 주는 것이다. 통지가 오는 형태는 메시지이기 때문에, 클립보드 표시기는 응당 윈도우를 생성하고 메시지 loop을 돌고 있어야 한다.

자신(윈도우)을 클립보드 표시기로 등록하려면, WM_CREATE나 WM_INITDIALOG 같은 초기화 메시지에서 SetClipboardViewer 함수를 호출하여 자신의 핸들값을 전달하면 된다.
그러면 그 뒤부터는 어떤 프로그램에서든 클립보드의 내용을 건드린 뒤 CloseClipboard 함수를 호출해 주면, 내 창으로 WM_DRAWCLIPBOARD 메시지가 날아온다. 그럼 내 프로그램은 그때 클립보드 내용을 들여다보면서 적절한 출력을 해 주면 된다.

그런데 문제는 이게 전부가 아니라는 것이다.
클립보드 표시기 API는 엄청난 구시대 스타일로 굉장히 구리게 설계되어 있다. Windows API를 통틀어서 이 정도로 지저분한 물건은 흔치 않을 것 같다.

클립보드 변경 통지 요청을 한 윈도우는 우리 프로그램뿐만이 아니라 여러 개가 동시에 있을 수 있다. 그러니 운영체제는 그 윈도우들의 목록을 내부적으로 관리해야겠지만, 각각의 윈도우의 입장에서야 나 말고 다른 윈도우가 무엇이 있든 말든, 나만 통지를 곱게 받고 끝이어야 정상일 것이다.
그런데 클립보드 표시기 관련 API들은 그렇지 않다. 클립보드 표시기로 등록된 창들은 일종의 단방향 연결 리스트의 형태로 관리되는데, 운영체제는 그 리스트의 head 노드만을 갖고 있다. 그 뒤 나의 다음으로는 무슨 창이 있는지 관리를 해당 응용 프로그램이 직접 해야만 한다.. -_-;;;

SetClipboardViewer 함수는 인자로 받은 윈도우를 연결 리스트의 맨 앞 head 노드로 등록한 뒤, 예전에 head였던 윈도우 핸들을 되돌린다. 우리는 그 값을 반드시 따로 보관해 둬야 한다.

hwndNextCBViewer = SetClipboardViewer(hMyWindow);

그리고 내가 WM_DRAWCLIPBOARD 메시지를 받았다면, 우리는 자체 처리를 마친 뒤에 그 메시지를 저 창에다가 수동으로 전해 줘야 한다.

if(hwndNextCBViewer) SendMessage(hwndNextCBViewer, uMsg, wParam, lParam);
(uMsg는 어차피 WM_DRAWCLIPBOARD이고, wParam과 lParam은 쓰이지 않기 때문에 값이 모두 0임)

메시지를 DefWindowProc로 넘긴다 해도 이 일을 운영체제가 알아서 해 주지 않는다. 우리가 저렇게 메시지를 안 보내 주면 다음 클립보드 표시기들은 클립보드의 변경 내역을 전달받지 못하게 되어 동작이 죄다 꼬이고 만다!

내가 제어를 운영체제로 신속하게 돌려 주지 않으면 운영체제 전체를 다운시킬 수 있던 협력형 멀티태스킹의 암울한 냄새가 물씬 풍긴다.
훅 프로시저는 CallNextHookEx를 반드시 호출해 줘야 하는 것과 같은 스타일이기도 하고 말이다.

내 윈도우가 없어질 때(WM_DESTROY) 클립보드 표시기 지정 해제도 당연히 수동으로 해야 하는데, 이때 사용하는 함수는 ChangeClipboardChain이다. 얘에다가 내 윈도우뿐만 아니라 처음에 SetClipboardViewer의 리턴값으로 받았던 나의 다음 노드 윈도우도 같이 전해 줘야 한다. 마치 옛날에 C++에서 소멸자 함수가 존재하는 객체들의 동적 배열을 delete []연산자로 해제할 때, 배열 원소의 개수를 수동으로 전해 줘야 했던 것만큼이나 번거롭다.

ChangeClipboardChain(hMyWindow, hwndNextCBViewer);

그러면 운영체제는 자신이 내부적으로 갖고 있는 연결 리스트의 head 노드에 속하는 윈도우에다 WM_CHANGECBCHAIN 메시지를 보낸다. wParam에는 해제되는 윈도우, lParam에는 그 해제되는 윈도우의 다음 노드 윈도우가 들어있다.

클립보드 표시기 윈도우는 이 메시지도 살펴봐서 만약 내가 갖고 있는 '다음 노드' 값이 등록 해제되는 윈도우(wParam - hwRemove)라면, 나의 '다음 노드' 값을 등록 해제되는 윈도우의 다음 윈도우(lParam - hwNext)로 업데이트하면 된다. 물론, 나 자신이 등록 해제되고 있다면 저런 메시지 따위는 오지 않고 말이다. 아래의 소스 코드를 참고하라.

void On_WM_CHANGECBCHAIN(HWND hwRemove, HWND hwNext)
{
    if(hwndNextCBViewer==hwRemove) hwndNextCBViewer=hwNext;
    else if(hwndNextCBViewer) SendMessage(hwndNextCBViewer, uMsg, wParam, lParam);
}

hwRemove가 나의 다음 윈도우에 해당한다면 다음 윈도우를 그 다음 것으로 업데이트하고 처리를 종결한다.
그렇지 않으면 아까 WM_DRAWCLIPBOARD를 포워딩했던 것처럼 동일 메시지를 다음 윈도우로 전달해 준다.

연결 리스트에서 어떤 노드를 삭제하기 위해서는 그 노드의 이전 노드가 가리키는 다음 노드를 고쳐 줘야 한다. 그러나 클립보드 표시기 chain은 이전 노드 정보가 존재하는 이중 연결 리스트가 아니라, 오로지 '다음' 노드 정보만이 존재하는 단일 연결 리스트이다.
그렇기 때문에 임의의 노드를 삭제하려면 이전 노드를 파악하기 위해 리스트를 처음부터 다 조회해야 하고, 결과적으로 시간 복잡도 O(n)에 해당하는 절차가 필요해진 것이다. 그것도 운영체제가 알아서 처리해 주는 게 아니라 응용 프로그램들이 다 협조해 줘야 하는 번거로운 형태이고 말이다.

요컨대 클립보드의 내용을 실시간으로 업데이트하여 표시하는 프로그램이라면 최소한 나의 다음 윈도우 정보는 보관해야 하며, WM_DRAWCLIPBOARD와 WM_CHANGECBCHAIN 메시지를 정석대로 처리해 줘야 한다. 내가 프로그램을 잘못 짜면 다른 프로그램의 동작까지 망칠 수가 있으니 이건 운영체제의 보안 관점에서도 굉장히 안 좋은 디자인이다..

운영체제가 달랑 갖고 있는 클립보드 표시기 chain의 head 노드 윈도우를 되돌리는 GetClipboardViewer라는 함수도 있다. 얘는 가장 마지막으로 SetClipboardViewer함수를 호출한 윈도우의 핸들을 되돌리는 셈인데, 이 윈도우로부터 다음 윈도우를 알 수 있는 것도 아니고(다음 윈도우 핸들은 각 창마다 고유한 방식으로 저장하고 있을 테니), 이 함수는 사실상 아무짝에도 쓸모가 없다.

나 같으면, 표시기 윈도우 리스트의 관리를 운영체제가 전적으로 알아서 해 주고 WM_CHANGECBCHAIN 처리를 할 필요가 없는 새로운 SetClipboardViewerEx 함수라도 만들 것 같다. 새로운 응용 프로그램은 더 깔끔한 새로운 API를 쓰라고 말이다. 서브클래싱만 해도 더 깔끔하게 하라고 Windows XP부터는 종전의 SetWindowLongPtr을 대체할 SetWindowSubclass 같은 함수가 새로 추가되지 않았던가.

(* 2017. 7. 14 추가)
그렇게 생각했는데, 최신 MSDN을 우연히 뒤져 보니 역시나 AddClipboardFormatListener라고 내가 생각하는 것과 개념상 정확히 동일한 함수가 Windows Vista에서부터 추가됐구나. 저건 클립보드 내용이 변경될 때마다 내 윈도우로 통지 메시지가 오게 하는 함수로, 예전 같은 번거로운 chain 관리가 필요하지 않다. 등록이 아닌 제거는 Add 대신 Remove로 시작한다. 게다가 실제로 변경된 포맷이 무엇인지도 GetUpdatedClipboardFormats라는 함수로 알아올 수 있다.

이 새로운 listener에 등록되고 나면 클립보드가 변경되었을 때 WM_CLIPBOARDUPDATE라는 메시지가 날아온다. 안 그래도 1024개밖에 안 되는 시스템 메시지 영역은 부족해서 난리일 텐데.. WPARAM, LPARAM 아무 용도가 없는 새로운 메시지를 굳이 추가할 필요가 있나 싶은 생각이 든다. 기존의 WM_DRAWCLIPBOARD도 인자가 전혀 쓰이지 않으며, 메시지를 받는 클라이언트의 입장에서는 용도가 정확하게 동일할 텐데 말이다. 뭐 확실한 구분을 위해서 메시지도 따로 만든 것이지 싶다.
아울러, GetClipboardSequenceNumber라는 함수도 있다. 얘는 클립보드 내용이 변경될 때마다 1씩 증가하는 시퀀스 번호를 되돌리며, Vista가 아니라 2000 시절부터 존재해 온 물건이다.

이걸로도 모자라서 나만의 클립보드 포맷을 등록하여 그 내용을 화면에다 어떻게 표시할지까지 시시콜콜하게 다 지정하는 규격도 Windows API에 있긴 하다. 거기까지 가면 실생활에서 쓰이는 일은 정말 거의 없다시피한 잉여이다.

Posted by 사무엘

2013/09/12 08:29 2013/09/12 08:29
,
Response
No Trackback , 3 Comments
RSS :
http://moogi.new21.org/tc/rss/response/876

수학에서 행렬은 굉장히 흥미로운 물건이다.
행렬끼리의 덧셈이나 행렬의 상수배는 어려울 게 없는 쉬운 연산이지만, 행렬끼리의 곱셈은 그렇지 않다. 행렬 A와 B사이의 곱셈은 A의 가로 크기와 B의 세로 크기가 같아야 정의되며, 새로 생기는 행렬의 크기(dimension)는 반대로 B의 가로 크기와 A의 세로 크기로 결정된다.

이런 특성상 행렬의 크기는 세로, 즉 row부터 먼저 써 주는 게 직관적이다. 세로 x줄 가로 y줄짜리 x,y 행렬과 y,z 행렬의 곱은 x,z 크기가 된다고 표기가 가능하기 때문이다.

또한, 앞에 있는 행렬과 뒤에 있는 행렬이 원소가 서로 연산되는 방향이 다르기 때문에 행렬의 곱셈은 교환 법칙이 성립하지 않는다. A×B가 일반적으로 B×A와 같지 않다는 뜻. 그러나 결합 법칙은 성립한다. (A×B)×C와 A×(B×C)는 동일하므로, 같은 방향만 유지하면 아무 순서로나 행렬을 곱해 줘도 된다.

그래서 이것과 관련하여 흥미로운 문제가 하나 있다.
크기가 들쭉날쭉 다르지만 순서대로 곱셈은 가능한(= 인접한 행렬끼리는 앞 행렬의 가로 크기와 뒤 행렬의 세로 크기가 일치) N개의 행렬들이 있다. 우리는 이들을 모두 최소의 계산량만으로 곱하고 싶다.

역행렬이나 행렬식 값을 구하는 비용에 비할 바는 아니겠지만 행렬의 곱셈은 꽤 비싼 연산이다. 일반적으로 x,y 크기와 y,z 크기의 행렬을 곱하는 데는 원소들간에 x*y*z회의 곱셈이 필요하다. n 크기의 정사각행렬의 경우 이는 n^3으로 귀착된다. (뭐, 분할 정복법을 활용하여 n^2.x승으로 줄이는 복잡한 알고리즘이 있긴 하지만 이것은 초기 준비 오버헤드가 굉장히 크기 때문에 행렬이 무진장 클 때에나 의미가 있다.)

예를 들어 A는 4*2 크기, B는 2*3 크기, C는 3*1크기의 행렬/벡터라고 치자.
이것을 A*B*C 순으로 진짜 순서대로만 곱하면 A*B를 곱하는 데 4*2*3=24회의 곱셈이 동원되고, 그 결과물인 4*3 행렬을 C와 곱하느라 12회의 곱셈이 필요해서 계산량은 총 36이 된다.

사용자 삽입 이미지

그러나 B*C부터 먼저 곱한 뒤 A를 거기에다 곱하면 열수가 적은 C 덕분에 B*C는 겨우 6회 만으로 끝나고, 거기에다 4*2*1=8회의 곱셈이 추가되어 총 14의 계산량만으로 A*B*C를 구할 수 있다. 답은 결국 똑같은데도 (AB)C보다 A(BC)가 훨씬 더 나은 전략인 것이다.

신기하지 않은가? 그래서 이런 configuration을 일반화하여 {4, 2, 3, 1}이라고 표현하고, 더 나아가 n>=3인 n개의 자연수라고 치자.
이 입력에 대해서 최소 곱셈 횟수와 실제 곱셈 순서를 구하는 것이 문제이다.

정올 공부를 한 분이라면 아시겠지만, 이것은 다이나믹 프로그래밍, 혹은 동적 계획법이라는 알고리즘 설계 방법론을 학습하면서 예시로 다뤄지는 아주 기본 문제이다. 다이나믹 프로그래밍은 다음과 같은 경우에 유용하다.

  • 전체 구간에 대한 최적해가 부분 구간의 최적해에다가 추가 연산을 함으로써 구하는 게 가능하다.
  • 그리고 한번 답을 구해 놓은 부분 구간의 최적해는 더 바뀌지 않는다는 게 보장된다.

이 행렬의 곱셈 문제에서 가장 작은 구간은 3이며, 이때의 답은 그냥 두 말할 나위 없이 세 정수의 곱이다.
그리고 전체 구간 [1..n]에 대해서 최적해는 바로..

  • 1을 [2..n]과 곱했을 때의 계산량 (맨 앞의 행렬과 나머지)
  • [1..n-1] 과 n을 곱했을 때의 계산량 (앞의 행렬들과 맨 뒤의 행렬)

중 더 작은 놈이라고 간주하면 된다.

그럼 [2..n]과 [1..n-1]은? 각 구간에 대해서 또 동일한 해법을 적용하여 재귀적으로 구간을 계속 쪼개 나가는 것이다. 언제까지? 구간의 길이가 3이 될 때까지 말이다.
이렇듯, 다이나믹 프로그래밍은 재귀성을 띠고 있다. 이것은 수학적으로는 점화식으로 표현되며, 코드로는...

const int dat[]={4,2,3,1,2,6,5,8,3,2}; //배열

int GetMin(int f, int t)
{
    int i=t-f, j;
    if(i<3) return 0; //should not reach here
    else if(i==3) return dat[f]*dat[f+1]*dat[f+2]; //obvious case
    else {
        //사실은 i가 3인 경우도 이 조건의 특수한 케이스라고 간주할 수 있다.
        //단지 GetMin값이 0이고, t-2와 f+1이 동일한 값이 될 뿐이다.
        i=GetMin(f,t-1) + dat[f]*dat[t-2]*dat[t-1]; //(A*B)*C
        j=GetMin(f+1,t) + dat[f]*dat[f+1]*dat[t-1]; //A*(B*C)
        return i<j ? i:j;
    }
}

int answer = GetMin(0, 10);

과연 이렇게 하면 답이 구해질까?
프로그램을 돌려 보면, 10개의 정수로 표현된 9개의 서로 다른 크기의 행렬들의 곱은..
146회의 곱셈만으로 계산이 가능하다고 나온다.

구체적인 계산 순서는 이러하다.

4 (2 (3 (((((1 2 6) 5) 8) 3) 2)))

이 경우, 각 단계별 계산 순서는 다음과 같이 되기 때문에,

x y z x*y*z
1 2 6 12
1 6 5 30
1 5 8 40
1 8 3 24
1 3 2 6
3 1 2 6
2 3 2 12
4 2 2 16

곱을 전부 합하면 진짜로 146이 맞다!
참고로, 이런 전략을 쓰지 않고 진짜 FM대로 앞에서부터 뒤로 행렬을 순서대로만 곱하면 계산량은 최적해의 세 배를 넘는 492에 달한다.
이것이 바로 알고리즘이 만들어 내는 차이이다.

다이나믹 프로그래밍에는 반드시 수반되어야 하는 작업이 있다. 바로 예전에 구했던 구간 계산값들을 배열에다 저장해 두는 것이다. 그렇게 하지 않으면, 마치 피보나치 수열을 f(x) = f(x-1)+f(x-2)라고만 구현하는 것만큼이나 계산량이 n이 커짐에 따라 기하급수적으로 커지게 된다. 그것도 예전에 한번 했던 똑같은 계산을 매번 반복하느라 말이다.
그래서 이 방법을 사용한 알고리즘은 대체로 시간 복잡도와 공간 복잡도가 모두 O(n^2)이 된다. 시간 복잡도가 지수함수에서 그래도 다항함수로 바뀐다.

구간별로 최적해 자체뿐만이 아니라 구간 분할을 어떻게 했는지에 대한 정보도 따로 보관해 놓으면 아까와 같은 구체적인 계산 순서도 그 정보를 추적함으로써 구할 수 있다.

정올에서 다이나믹 프로그래밍의 중요성은.. 두 말하면 잔소리이다.
본인은 20세기에 정올 공부를 한 세대인지라 그 시절의 문제밖에 기억을 못 한다만..

1997년 한국 정보 올림피아드의 고등부 3번인 벽장 문제는 최적해를 구하고자 할 경우 공간과 시간 복잡도가 O(n^3)인 다이나믹 프로그래밍으로 풀 수 있다. 이 때문에, 16비트 환경임을 감안하더라도 이 문제는 입력의 범위가 작다. 벽장의 개수와 벽장 사용 순서가 최대 겨우 20까지밖에 안 올라가는 소규모이다. 실용적인 상황에서는 이런 부류의 시뮬레이션 문제는 휴리스틱이 동원되어야 할 것이다.

이 외에,

1999년 고등부 1번 검은 점 흰 점 연결,
2000년 고등부 1번 수열 축소

도 다이나믹으로 푸는 문제이다.
국제 정보 올림피아드의 기출 문제 중에는
10회(1998)의 둘째 날 마지막 문제인 폴리곤 게임,
11회(1999)의 첫째 날 첫 문제인 꽃 진열이 기억에 남는다. 특히 꽃 진열은 상당히 기초적인 다이나믹 프로그래밍 문제로, <날개셋> 타자연습의 문장 정확도 측정도 이와 거의 같은 발상의 알고리즘을 사용하고 있다.

난 이 바닥은 손 놓은 지가 너무 오래 돼서 기억이 가물가물하다.
정보 올림피아드에서 경시와 공모는 마치 과학과 공학, 어학과 문학의 차이와 비슷한 것 같다.

Posted by 사무엘

2013/08/14 08:34 2013/08/14 08:34
, ,
Response
No Trackback , 8 Comments
RSS :
http://moogi.new21.org/tc/rss/response/866

한자어로 '원'이라고 부르는 동그라미라는 도형은 시각적으로나 수학적으로나 아주 신기한 도형이다.
둥글다는 게 무슨 의미인지 기계가 계산으로 표현할 수 있을 정도로 엄밀하게 정의하자면 결국 '어떤 점에서 거리가 같은 점들의 집합'이라는 정의가 등장하게 되고, n차원 직교 좌표에서 거리라는 건 결국 차원을 구성하는 각 축의 거리들의 제곱의 합의 제곱근이라고 정의된다.

원의 지름과 원의 둘레의 비율은 그 이름도 유명한 '파이'이며, 3.141592... 로 시작하는 이 값은 무리수인 동시에 초월수라는 것도 상식이다.

그런데 이 원을 정사각형 격자 모양의 래스터 그래픽 장치에서 어떻게 하면 효율적으로 그릴 수 있을까? 그런 물건의 내부엔 컴퍼스 같은 직관적인 도구가 없는데 말이다.
중심이 x, y이고 반지름이 r인 원을 구성하는 좌표들을 어떤 계산을 통해 얻어 올 수 있을까?
원점이 중심인 원의 방정식은 x^2+y^2=r^2. 따라서 y=sqrt(r^2-x^2) 방정식을 이용하면 사분원 내지 반원을 구성하는 점을 구할 수 있다. 그리고 이 값을 바탕으로 나머지 방향의 점을 그리면 될 것이다.

#include <math.h>
template<typename T>
void Draw_Circle(int x, int y, int r, T f)
{
    double R_2 = r*r;
    for(int i=0;i<r;i++) {
        int v = (int)(sqrt( R_2 - i*i )+0.5);
        f(x-i, y-v); f(x-i, y+v);
        f(x+i, y-v); f(x+i, y+v);
    }
}

for문 자체는 0부터 r까지 사분원의 x좌표만 돌고, 이를 바탕으로 점을 찍는 함수 f를 4개 방향으로 모두 호출한다.
r의 제곱 값은 한 번만 계산하면 되므로 for문 밖에서 별도로 선언해 주는 센스도.
소숫점은 버림이 아니라 반올림이 되도록 0.5를 더한 뒤에 int로 캐스팅하는 게 좋다. 그래야 당장 그려지는 원도 90*n도 부근이 더 탱탱하고 보기 좋아진다.

함수의 사용은 MFC 기준으로 이런 식으로 하면 된다. 함수 안에서 또 다른 함수를 내부적으로 호출할 때 함수 포인터보다 람다가 참 깔끔하긴 하다. (너무 남발한 게 꼬이면 code bloat은 피할 수 없겠지만)

CPaintDC dc(this);
auto x = [&](int x,int y) { dc.SetPixel(x,y,0); };
Draw_Circle(220,220, 200,  x);
Draw_Circle(420,330, 160,  x);

사용자 삽입 이미지

그런데 아뿔싸, 역시 기울기가 1보다 더 커지는 곳에는 점이 듬성듬성 떨어져 있게 된다.
이 틈을 점 찍기가 아니라 선 그리기 같은 다른 함수로 메운다는 건 있을 수 없는 일이고..
결국, 우리의 원 그리기 알고리즘은 언제나 기울기가 1보다 작은 구간에서만 동작하게 loop 구조를 바꿀 필요가 있다.
우리는 원을 4등분했는데, 그렇게 4등분된 조각도 한쪽 끝과 맞은편 끝이 완벽하게 대칭으로 이들을 동시에 그려 보자.

가령, 1사분면에서는 x좌표를 1씩 증가시키면서 r로 근접하고(위의 코드에서 i) y좌표는 r이다가 점점 0으로 작아지는데(위의 코드에서 v),
이와 동시에 반대편에서는 y좌표를 1씩 증가시키면서 r로 근접하고, x좌표는 r에서 0으로 근접시키도록 점을 같이 그리는 것이다.
이제 loop는 변수 i의 값이 r에 도달한 지점에서 끝나는 게 아니라 v와 값이 같아지는 지점에서 끝나면 된다. (정확히는 sqrt(2)*r/2 지점이 됨)

{
    double R_2 = r*r;
    for(int i=0; ;i++) {
        int v = (int)(sqrt( R_2 - i*i )+0.5);
        f(x-i, y-v); f(x-v, y-i);
        f(x-i, y+v); f(x-v, y+i);

        f(x+i, y-v); f(x+v, y-i);
        f(x+i, y+v); f(x+v, y+i);
        if(i>v) break;
    }
}

사용자 삽입 이미지
와, 이로써 굉장히 찰진 모양의 원이 그려졌다. 한 번 루프를 돌 때마다 점이 8개가 그려지는 것이다.
그러나 이런 원 하나 그리는데 부동소숫점에, 곱셈에, 심지어 제곱근까지 꽤 부담스러운 연산이 많이 들어갔다.
이걸 좀 줄일 수는 없을까?

...
    int R_2 = r*r;
    int v = r;
    for(int i=0; ;i++) {
        if(i*i + v*v > R_2) --v;
...

loop의 앞부분을 이렇게 고쳐 보자.
x축에 속하는 i의 값이 1증가할 때마다 y축에 속하는 v의 값은 그대로 유지되거나 1 감소하거나 둘 중 한 변화만을 겪을 것이다.
i가 증가함에 따라 원점에서 i, v까지의 거리가 R보다 확 커지게 됐다면, 이 궤적은 원의 범위를 벗어나는 것이므로 y축에 속하는 v를 1 줄여 준다.

실질적으로 행해지는 연산을 이렇게 최적화해 주면 최소한 부동소숫점과 제곱근 연산은 없어진다.
그러나 최적화의 여지는 그래도 여전히 남아 있다. 저 꼴도 보기 싫은 곱셈을 없애려면 어떡하면 좋을까?

방법이 있다.
결국, i*i는 0, 1, 4, 9, 16 ...의 순열을 생성해 낼 텐데, 얘는 덧셈을 두 번 하는 걸로 대체할 수 있다. 한 번 덧셈을 한 뒤엔 증가치가 2씩 늘어나니까 말이다(1과 4의 차는 3, 4와 9의 차는 5, 9와 16의 차는 7). x^2의 도함수가 괜히 2*x가 아니다.

그리고 v는 초기값이 아예 R_2와 같으니 약분이 가능하다. 그 뒤에 v의 값이 줄어들면서 차이만이 발생할 뿐이다. 그런데 얼마를 빼 줘야 할까?
x^2가 (x-1)^2로 바뀌었을 때 감소하는 값은 잘 알다시피 2*x-1이다. 따라서 이 값만 초기에 계산해 놓은 뒤, v가 1 감소하게 됐을 때 가상의 v_square은 그만치 빼 주고, 그 델타값 자체도 2 감소시키면 된다.

...
    int v = r, i_square = 0, i_delta = 1;
    int v_delta=2*r-1, v_square_delta = 0;
    for(int i=0; ;i++) {
        if(i_square + v_square_delta > 0) {
            --v; v_square_delta-=v_delta, v_delta-=2;
        }

... //점 여덟 군데를 찍어 준 뒤

        if(i>v) break;
        else i_square+=i_delta, i_delta+=2;
    }

이로써 그 부드러운 원을 오로지 정수의 덧셈만으로, 그리고 곱셈이라고는 loop 돌기 전에 *2 단 한 번밖에 안 하는 깔끔한 원 그리기 알고리즘이 완성되었다. 놀랍지 않은가? 게다가 고정적인 두 배 연산은 잘 알다시피 bit shift로도 수행 가능한 아주 가벼운 연산이기도 하고 말이다.

GWBASIC, Windows GDI API, 옛날 볼랜드 BGI 등 모든 그래픽 라이브러리에 들어있는 원 그리기 함수는 기본적으로 이 알고리즘을 이용하여 원을 그린다. 각종 알고리즘 서적에 예제로 실려 있는 소스들도 세부적인 변수 활용이나 계수 계산에 차이가 있을지언정 기본적인 아이디어는 동일하다.

사실, 이건 거의 대학교 학부 수준이고 정보 올림피아드 공부라도 했다면 중· 고등학교 시절에라도 접했을 기초적인 내용이다. 진짜 어려운 건 이걸 응용하여 안티앨리어싱을 적용한다거나 타원을 그리거나, 아예 부채꼴 내지 회전된 원을 그리는 알고리즘이다.

단, Windows GDI가 그리는 원은 왠지 좀 엉성하고 덜 예쁜 것 같다. 비교를 할 때 반올림 보정을 안 하는지 경계가 아주 약간 덜 통통하며, 특히 기울기가 1(45도)에 가까워지는 지점에 점의 배치가 지저분하다.
차이를 보이기 위해 움짤을 만들어 보았다. 파란색 원은 GDI 함수로 그린 것이고, 빨간색 원은 우리가 작성한 함수로 그린 것이다.

사용자 삽입 이미지

Posted by 사무엘

2013/07/28 08:27 2013/07/28 08:27
, , ,
Response
No Trackback , 6 Comments
RSS :
http://moogi.new21.org/tc/rss/response/860

« Previous : 1 : ... 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : ... 29 : Next »

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2022/01   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          

Site Stats

Total hits:
1729684
Today:
326
Yesterday:
406