온라인 개인맞춤형 SIGMA!!
Blog | Tag | Local | Guest | Login | Write |  RSS
분류 전체보기에 해당되는 글 110건
2008.12.11 :: 디바이스 드라이버 70
2008.12.09 :: 시뮬레이션 시작하기.(로봇 연결) 104
2008.12.09 :: Dot Font Generator 1
2008.12.08 :: GTK+의 Menu Widget
2008.12.07 :: 컴퓨터 구조 명령어 사이클
2008.12.07 :: 컴퓨터 구조 타이밍과 제어 이야기
2008.12.06 :: Indentation & Blank space
2008.12.04 :: 알고리즘 코딩기법 - 7. Bit 연산 Brute Force
2008.12.03 :: Verilog HDL 2. 문법
2008.12.02 :: VPL 기본 4. if 조건문, switch 조건문 처리. 3358
디바이스 드라이버
2008. 12. 11. 00:17 :: Hardware Basic

 

하드웨어 개발자의 종착역은 결국, 디바이스 드라이버가 됩니다.
처음엔 땜질을 하면서 이것저것 배우게 되고,
그 다음에는 기본적인 MCU를 배우게 됩니다.
이때 인터럽트라는 개념에서 한 번 뱅글뱅글 돌게 되지요.
그러다가 이제는 설정 레지스터 에서 뱅글뱅글 돌게 되고요...
이렇게 저렇게 발전 하다보면, OS의 필요성을 절실히 느끼게 됩니다.
그만큼 성장을 해서 관리해야할 자원들이 많아지거든요..
그럼 스 자원 관리를 위해서 OS를 올리게 되는데
일반적으로 TinyOS - RTOS - linux 순으로 올라가게 됩니다.

리눅스를 올리게 되면 커널을 통해서 디바이스를 제어하게 되므로,
결국 리눅스 커널상에서 디바이스 드라이버가 돌아가게 만들어야 합니다.

아래 내용은 그 디바이스 드라이버에 대해서 간단하게나마 개념을 잡아주도록 설명을 해주고 있습니다.^^

 

 

디바이스 드라이버

아주 오래 전에는 컴퓨터에 달린 모든 장치에 대해 프로그래머가 모든 장치 제어에 대해 프로그램을 직접 작성해야 했습니다. 이러다 보니 프로그래머나 판매자, 사용자 모두 힘들었습니다. 예를 들어 아무리 좋거나 저렴한 프린터라도 프로그래머가 제어할 방법을 모른다면 사용할 수 없었습니다. 만일 사용자가 특정 제품을 사용하겠다고 고집하면 하는 수 없이 프로그래머는 학습과 코딩 수정이 필요했습니다.

그러나 디바이스 드라이버라는 개념이 생긴 후로는 프로그래머는 자신의 프로그램에 더욱 충실할 수 있었습니다. 즉, 외부 장치에 대해서는 제품을 만든 회사에서 함께 제공되는 드라이버를 이용하면 되기 때문입니다.

거기다가 이 드라이버를 사용하는 방법이 완전히 같지는 않아도 대동소이 하다면 그야말로 프로그래머는 장치에 대한 부담에서 많이 자유로워 질 것입니다.

우리가 흔히 디바이스 드라이버를 설명할 때 그리는 그림입니다. 하드웨어가 있고 그 안에 응용 프로그램이 실행되는데, 응용 프로그램에서 직접 하드웨어를 제어하는 것이 아니라 다비이스 드라이버를 통해 하드웨어를 제어합니다.

그러나 장치에 따라 디바이스 드라이버도 서로 다릅니다. 만들어진 회사도 다를 수 있습니다. 장치를 쉽게 다룰 수 있도록 디바이스 드라이버까지 만들어서 제공해 준 것 까지는 좋은데, 사용하는 방법이 디바이스 드라이버 마다 매우 다르다면 응용 프로그래머에게는 부담이 매우 클 것입니다.

리눅스에서는 모든 장치를 파일을 다루듯이 사용할 수 있다라는 말씀을 많이 들으셨을 것입니다. 리눅스에서는 디바이스 드라이버를 파일처럼 다룰 수 있도록 가상 파일 시스템(Virute File System)을 제공하기 때문에 가능한 것입니다.

 

디바이스 드라이버 사용 예

가상 파일 시스템이라는 내용을 이해해 보도록 하겠습니다. 이전에 시리얼 통신 강좌 시리즈 중에 시리얼 통신 - 통신포트 열기 글에서 디바이스 드라이버에 대해 말씀을 드린 적이 있습니다. 그 중에 일부를 올립니다.

시리얼 포트의 장치명

/dev 디렉토리에 있는 시리얼 포트의 목록을 보면 아래와 같은 내용이 출력됩니다. 도대체 뭔소리인지 하나씩 알아 보겠습니다.

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
crwxrwxrwx 1 root tty 4 64 Jan 1 2006 ttyS00
crwxrwxrwx 1 root tty 4 65 Jan 1 2006 ttyS01
crwxrwxrwx 1 root tty 4 66 Jan 1 2006 ttyS02
crwxrwxrwx 1 root tty 4 67 Jan 1 2006 ttyS03

(1) 접근 권한을 보면 crwxrwxrwx 로 c로 시작하는 것은 장치가 "문자 장치"임을 알려 줍니다. c 가 아닌 b로 시작한다면 "블록 장치"를 말하는데, 예로 하드디스크와 같이 블럭 단위로 읽거나 쓰기를 하는 장치가 되겠습니다.

(5) 의 4는 메이저 장치 번호, (6)의 64, 65, 66 등은 마이너 장치 번호입니다. 우리가 작성하는 프로그램은 하드웨어 장치를 직접 제어하는 것이 아니라 커널을 통해 제어하게 됩니다. 하드웨어를 파일 개념으로 처리할 수 있는 것도 중간에 커널이 가상 파일을 만들어서 제공하기 때문에 가능 한 것입니다.

프로그램에서 하드웨어 장치에 대해 어떤 작업을 커널에게 요청하면, 커널은 메이저 번호를 가지고 어떤 디바이스 드라이버 사용할 지를 결정하게 됩니다. 디바이스 드라이버는 커널로부터 받은 정보 중 마이너 장치 번호를 가지고 자기에게 할당 된 장치 중 어떤 장치를 제어할 지를 결정하게 됩니다.

위의 장치 목록을 보시면 메이저 번호가 모두 4 로 똑 같습니다. 대신에 마이너 번호만 다르죠. 커널은 메이저 번호로 따라 디바이 드라이버를 선택하고 다음 처리를 넘기면 디바이스 드라이버는 마이너 번호를 가지고 어느 장치를 사용할 지를 결정한다는 얘기가 되겠습니다.

이렇게 하드웨어 장치 제어 흐름을 본다면 ttyS0, ttyS1 과 같은 이름은 별로 중요하지 않죠. 중요한 것은 메이저 장치 번호와 마이너 장치 번호가 되겠습니다.

위 내용을 조금 더 쉽게 이해하기 위해 통신 포트를 open 하는, 즉 통신 포트를 사용하기 위한 프로그램 코드를 보겠습니다.

fd = open( "/dev/ttyS0", O_RDWR | O_NOCTTY | O_NONBLOCK );

통신 포트라는 장치를 사용하기 위해서 /dev/ttyS0를 open했습니다. 그렇다면 /dev/ttyS0 가 디바이스 드라이버일까요? 디바이스 드라이버도 응용프로그램과 장치 사이에서 실행되는 프로그램이라고 생각한다면 /dev 에서 장치 목록을 출력할 때, 주 장치 번호와 부 장치 번호 뿐만 아니라 파일 사이즈도 나와야 할 것입니다. 파일 사이즈도 파이에 대한 중요 정보이니까요.

그리고 만약에 /dev/ttyS0 가 디바이스 드라이버라면 문제가 있습니다. 예로 시리얼포트가 8개가 있다고 한다면,

]$ ls -al | grep ttyS
crw-rw----   1 root uucp     4,  64  7월  3 14:18 ttyS0
crw-rw----   1 root uucp     4,  65  7월  3 14:18 ttyS1
crw-rw----   1 root uucp     4,  66  7월  3  2007 ttyS2
crw-rw----   1 root uucp     4,  67  7월  3  2007 ttyS3
crw-rw----   1 root uucp     4,  68  7월  3  2007 ttyS4
crw-rw----   1 root uucp     4,  69  7월  3  2007 ttyS5
crw-rw----   1 root uucp     4,  70  7월  3  2007 ttyS6
crw-rw----   1 root uucp     4,  71  7월  3  2007 ttyS7

이렇게 통신 포트별로 이름을 바꾸면서 다비이스 드라이버를 작성해서 올려야 합니다. 포트 번호만 다르고 처리하는 방법은 같은데, 통신 포트 개수만큼 소스를 수정하고 모두 컴파일해서 등록해야 된다면 매우 불편할 것입니다.

insmod

그래서 실제로는 하나의 디바이스 드라이버를 만들어서 커널을 올립니다. 커널을 올릴 때, 다른 디바이스 드라이버와 구별할 수 있도록 번호를 앞 가슴에다 부착하고 커널에 올립니다. 이 번호가 주 장치 번호, 주 번호가 되겠습니다.

insmod user_device_name

이렇게 insmod 명령을 실행하면 user_device_name 디바이스 드라이버 안에 주 번호를 몇 번으로 등록할 지 커널에 요청하는 코드가 들어 있습니다. 즉, user_device_name 디바이스 드라이버를 만들 때부터 프로그래머에 의해 주 장치 번호가 경정됩니다. 커널은 디바이스 드라이버에서 요청하는 장치 번호로 user_device_name 디바이스 드라이버를 커널 영역으로 로드합니다.

여기 글에서는 user_device_name 가 주 번호를 250을 사용한다고 하겠습니다.

mknod

이제 커널에서는 디바이스 드라이버를 사용할 준비가 되었습니다. 그러나 아직 커널만 알고 밖에서는 아무도 모릅니다. 커널 밖에서도 이 디바이스 드라이버를 사용할 수 있도록 공개해 주어야 하는데, 그냥 공개하기 보다는 응용 프로그램이 접근하기 쉽도록, 또한 같은 장치이면서 내부에 처리하는 번호가 다르다면 하나의 디바이스 드라이버에서 모두 처리할 수 있도록, 결국 응용프로그램에서 쉽게 사용할 수 있도록 가상 파일 시스템으로 제공해 줍니다.

그것이 바로 /dev/장치명이 되겠습니다.

]# mknod /dev/user_device_S0 c 250 0
]# mknod /dev/user_device_S1 c 250 1
]# mknod /dev/user_device_S2 c 250 2
]# mknod /dev/user_device_S3 c 250 3
]# mknod /dev/user_device_S4 c 250 4

/dev 안에 있는 아이템을 계속 장치명이라고 말씀드렸습니다만 정확한 명칭이 node 라고 하더군요. 그래서 명령어 이름이 mknod 인것으로 생각됩니다.

응용프로램과 커널 그리고 디바이스 드라이버

자, 이제 응용프로그램에서 다시 보겠습니다.

fd = open( "/dev/ttyS0", O_RDWR | O_NOCTTY | O_NONBLOCK );

프로그램에서는 /dev/ttyS0 만 언급햇습니다. 실제 디바이스 드라이브 파일 명이 아닙니다. 이 프로그램 코드는 당연히 커널로 전송되어지고 커널에게 부탁하게 됩니다. 커널은 /dev/ttyS0에서 주 장치 번호를 확인합니다. 또한 주 장치를 보고 커널에 등록된 디바이스 드라이버중에 장치 번호에 해당하는 디바이스 드라이버를 찾아서 응용 프로그램의 open()에 대한 명령을 전송해 줍니다. 이때, 함께 전송되는 것이 /dev/ttyS0에 해당하는 부 장치 번호입니다.

디바이스 드라이버는 커널로부터 받은 부 장치 번호를 가지고 자신이 처리하는 여러 장치 중 어느 장치를 처리할 지를 파단하게 됩니다.

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
crwxrwxrwx 1 root tty 4 64 Jan 1 2006 ttyS0
crwxrwxrwx 1 root tty 4 65 Jan 1 2006 ttyS1
crwxrwxrwx 1 root tty 4 66 Jan 1 2006 ttyS2
crwxrwxrwx 1 root tty 4 67 Jan 1 2006 ttyS3

즉, /dev/ttyS0 장치를 사용한다면,

  1. 커널은 /dev/ttyS0 의 주 장치 번호 4번에 해당하는 디바이스 드라이버를 찾고
  2. 디바이스 드라이버에 부 장치 번호 64를 전송해 주면,
  3. 디바이스 드라이버는 자기가 처리하는 여러 통신 포트 중에 부 장치 번호인 64로 처리할 포트를 알게 됩니다.


:
시뮬레이션 시작하기.(로봇 연결)
2008. 12. 9. 22:00 :: MSRDS

그동안 VPL만 주구장창 했군요.-_-;;;

정작 로봇은 보여드리지도 않고...;;

-_-;;



오늘은 로봇을 직접 조종할 수 있는 시뮬레이션 모드에 대해서 설명하겠습니다.

레고 마인드스톰 NXT로봇을 조종할 수 있게 하도록합니다.

음..

만들어져 있는 로봇을 시뮬레이션 하는 것은 쉽습니다.

먼저 VPL을 실행시키고 Diagram에 Simple Dashboard 와 Simulated Generic Differential Drive Activity를 추가합니다.

그 둘을 연결시킬 필요는 없습니다. 다만 SimulatedGenericDifferentialDrive Activity의 Config 정보만 수정하여주면 됩니다.


정보를 수정하기 위해  SimulatedGenericDifferentialDrive Activity를 클릭하여 주시고 화면 오른쪽에 보시면 Properities 창이 보일겁니다.

거기에서 두번째 항목인 Configuration을 보시면 선택가능한 항목들이 있는데 거기서 Use a manifest를 선택합니다.

선택하시면 아래에 Manifest를 선택할 수 있는 콤보박스가 생성됩니다.



Properities에서 import 버튼을 클릭하면 SimulatedGenericDifferentialDrive을 지원하는 서비스 목록들이 표시되는데, 거기에서 LEGO.NXT.Tribot.Simulation.manifest.xml을 선택합니다.



그러면 VPL에서 더 이상 선택할 것은 없습니다.

그리고 실행을 시켜줍니다. 그러면 윈도우 창이 두 개 뜰겁니다.

하나는 Simpledashboard가 실행된 화면이고, 하나는 시뮬레이션 실행화면입니다.

시뮬레이션 실행 화면에 보시면 LEGO NXT Tribot이 보일겁니다.




SimpleDashboard에서 시뮬레이션 로봇에 연결하고 제어해야 합니다. 그러기 위해서는 오른쪽 상단에 있는 Machine : 입력박스에 "localhost"를 입력하고 Connect합니다.



그러면 아래의 Sevice Directory 아래에 (LegoNXTMotorBase) /simulated... 라고 표시 된 항목이 추가 됩니다.


그 생성된 항목을 더블클릭하시면, 왼쪽 Differential Drive에 있는 Motor : 부분이 Motor : On 으로 변경됩니다.



그리고 그 윗 부분의 Drive 버튼을 클릭하고, 그 상태에서 위의 동그라미의 십자선 표시 그 부분이 조이스틱 역할을 하는데 그 것을 마우스로 클릭하며 움직여 보시면, 로봇이 시뮬레이션 화면 안에서 원하는 움직임 대로 움직이는 것을 볼 수 있습니다.


움직여서 장애물 옆으로 옮겨간 모습입니다.


카메라 화면 시점을 움직이고 싶으시면, 시뮬레이션 화면을 클릭하시고 마우스로 옮기면 상하좌우로 회전하고, 키보드의 화살표 키를 누르시면 앞뒤옆 등으로 움직입니다.

단순히 Activity 두 개만을 추가해서 이렇게 로봇을 시뮬레이션 상에서 제어 가능한데, 물론 LEGO NXT 말고도 다른 기본적으로 제공하는 로봇들을 제어가능합니다.




:
Dot Font Generator
2008. 12. 9. 16:15 :: Advanced WPF

안녕하세요. 이번시간에는 TextBlock에 표시되는 글자를 Pixel단위로 쪼개어 Dot Font로 활용하는 방법에 대해서 소개해 드리겠습니다. 방법이야 여러가지가 있겠지만 저는 RenderTargetBitmp을 사용해 텍스트의 이미지를 생성하고 해당 이미지를 MemoryStream으로 복사 한 뒤 픽셀 단위로 문자열에 해당하는 부분을 검출하는 방법을 사용했습니다. 아래는 시연동영상입니다.



Generate Text에 변환할 문자를 입력하고 적당히 Spacing 을 조절한 뒤 Generate 버튼을 누르면 변환이 이루어집니다. Result 부분에는 변환된 점의 좌표가 출력되면 Preview에는 해당 점을 직접 그렸을 경우 미리보기가 가능합니다. 소스코드는 아래와 같습니다. 이번 예제에서의 XAML은 대부분 UI구성과 관련된 내용만 포함 하고 있으므로 설명은 하지 않고 C#코드에서 실제 Dot Font를 생성하는 부분만 설명을 하도록 하겠습니다. (전체 소스코드는 첨부하도록 하겠습니다.)

아래는 C#코드입니다.

view plaincopy to clipboardprint?
  1. public partial class Window1 : Window   
  2. {   
  3.     public Window1()   
  4.     {   
  5.         InitializeComponent();   
  6.     }   
  7.   
  8.     private void BtnGenerate_Click(object sender, RoutedEventArgs e)   
  9.     {   
  10.   
  11.         ResultTextBlock.Text = TxtText.Text;   
  12.         List<POINT> Result = GenerateDotFont(ResultTextBlock, (int)SliderSpacing.Value);   
  13.         DrawDotFont(Result);   
  14.         LstResult.ItemsSource = Result;   
  15.               
  16.     }   
  17.   
  18.     public void DrawDotFont(List<POINT> DotFont)   
  19.     {   
  20.   
  21.         DrawingVisual DrawingVisual = new DrawingVisual();   
  22.         DrawingContext DrawingContext = DrawingVisual.RenderOpen();   
  23.   
  24.         foreach (Point Dot in DotFont)   
  25.         {   
  26.             DrawingContext.DrawRectangle(Brushes.White, null,   
  27.                 new Rect(Dot.X,Dot.Y,2,2));   
  28.         }   
  29.   
  30.         DrawingContext.Close();   
  31.   
  32.         RenderTargetBitmap bmp = new RenderTargetBitmap((int)ResultTextCanvas.Width, (int)ResultTextCanvas.Height, 96, 96, PixelFormats.Pbgra32);   
  33.         bmp.Render(DrawingVisual);   
  34.         ResultTextCanvas.Background = new ImageBrush(bmp);   
  35.   
  36.     }   
  37.   
  38.   
  39.   
  40.     public List<POINT> GenerateDotFont(TextBlock ReferenceTextBlock,int Space)   
  41.     {   
  42.   
  43.         int Width = (int)ReferenceTextBlock.Width;   
  44.         int Height = (int)ReferenceTextBlock.Height;   
  45.   
  46.         FormattedText text = new FormattedText(ReferenceTextBlock.Text,   
  47.                 CultureInfo.CurrentCulture,   
  48.                 FlowDirection.LeftToRight,   
  49.                 new Typeface(ReferenceTextBlock.FontFamily, ReferenceTextBlock.FontStyle, ReferenceTextBlock.FontWeight, ReferenceTextBlock.FontStretch),   
  50.                 ReferenceTextBlock.FontSize, ReferenceTextBlock.Foreground);   
  51.   
  52.         DrawingVisual DrawingVisual = new DrawingVisual();   
  53.         DrawingContext DrawingContext = DrawingVisual.RenderOpen();   
  54.         DrawingContext.DrawText(text, new Point(0, 0));   
  55.         DrawingContext.Close();   
  56.   
  57.         RenderTargetBitmap bmp = new RenderTargetBitmap(Width, Height, 96, 96, PixelFormats.Pbgra32);   
  58.         bmp.Render(DrawingVisual);   
  59.   
  60.         BmpBitmapEncoder Encoder = new BmpBitmapEncoder();   
  61.         Encoder.Frames.Add(BitmapFrame.Create(bmp));   
  62.   
  63.         MemoryStream MemoryStream = new MemoryStream();   
  64.         Encoder.Save(MemoryStream);   
  65.   
  66.         // Header Skip   
  67.         MemoryStream.Seek(54, SeekOrigin.Begin);   
  68.   
  69.         byte[] Buff = new byte[MemoryStream.Length - 54];   
  70.         MemoryStream.Read(Buff, 0, (int)(MemoryStream.Length - 54));   
  71.   
  72.         List<POINT> Result = new List<POINT>();   
  73.         int HeightOffSet = 0;   
  74.         for (int Y = 0; Y < Height; Y+=Space)   
  75.         {   
  76.             HeightOffSet = Width * Y;   
  77.   
  78.             for (int X = 0; X < Width; X+=Space)   
  79.             {   
  80.                 if (Buff[((HeightOffSet + X) << 2 )] == 255)   
  81.                     Result.Add(new Point(X, Height - Y));   
  82.   
  83.             }   
  84.         }   
  85.   
  86.         return Result;   
  87.   
  88.     }   
  89.   
  90. }  

코드를 보면 2가지 함수를 확인 하실 수 있을 것입니다. DrawDotFont는 List<Point> Type의 Dot Data가 포함된 DotList를 사용하여 Canvas에 DotFont를 그려주는 역할을 하며 GenerateDotFont는 ReferenceTextBlock의 정보에 맞춰 DotFont를 생성하는 역할을 합니다.

우리가 자세히 살펴봐야하는 함수는 GenerateDotFont 인데요, 아래와 같이 총 5개의 과정을 통해 시작됩니다.

1. DrawingVisual과 DrawingContext를 사용해서 TextVisual을 생성합니다.
2. RenderTargetBitmap을 사용하여 DrawingVisual객체를 렌더링 합니다.
3. 렌더링한 RenderTargetBitmap객체를 BmpBitmapEncoder를 사용하여 Bmp형식으로 변환합니다.
4. MemoryStream을 사용하여 Bmp로 변환된 객체의 픽셀정보를 가져옵니다.
5. Spacing만큼 픽셀을 건너 뛰면서 해당 픽셀이 글자 부분인지를 체크합니다.

다소 접하기 어려운 Class를 활용하는 예제라서 처음 보기에는 어려워 보일 수 있는 코드지만, 한줄한줄 따라가다보면 쉽게 이해하실 수 있을것입니다. 그럼 오늘 포스팅은 여기까지 하고 기타 질문은 리플이나 메일로 보내주시면 답변드리겠습니다.
(조만간 Dot Font를 활용한 예제를 올리도록 하겠습니다.)

전체 소스코드입니다.

DotFontGenerator.zip



:
GTK+의 Menu Widget
2008. 12. 8. 22:00 :: GTK+

오늘은 Menu를 수동적으로 만들어 보겠습니다. menu를 만드는 방법은 두가지가 있습니다. 두가지 방법은 menu factory를 사용하는 방법과 고전적인 방법이 있습니다. 고전적인 방법을 먼저 알아보는 것이 공부하는데 도움이 되겠죠? ^ ^;
그렇다고 menu factory를 사용하다고 나쁘다는 것은 아닙니다. 두가지 방법은 장단점이 있으니까 사용하실때는 그때 그때 상황에 맞는 장점을 이용하는 것이 좋겠지요?

수동적인 방법으로 몇 가지 wrapper 함수들을 써 가며 메뉴를 만드는 것이 유용성에 있어서 훨씬 유리함에도 불구하고, menufactory를 이용하는 방법은 훨씬 사용하기 쉽고 또 새로운 메뉴를 추가하기도 쉽습니다. Menufactory를 이용하게 되면, 메뉴에 이미지라든가 '/'를 쓰는 것이 불가능해집니다.

위에 말씀 드렸듯이, 오늘은 수동적으로 menu를 만드는 방법을 선보이겠습니다.

메뉴바와 하위메뉴(submenu)들를 만드는데 쓰는 세가지 widget이 있습니다.

메뉴 아이템(menu item) : 사용자가 선택하는 것. (예: 'Save')
메뉴(menu) : 메뉴 아이템들의 컨테이너.
메뉴바(menubar) : 각각의 메뉴들을 포함하는 컨테이너.

메뉴 아이템 widget이 두가지 다른 용도로 쓰일 수 있다는 점때문에 약간 복잡한 면이 있습니다. 메뉴 아이템은 단순히 메뉴 위에 놓일 수도 있고 또는 메뉴바 위에 놓여서 선택되었을 때 특정 메뉴를 활성화시키도록 쓰일 수도 있습니다.

메뉴와 메뉴바를 만들기 위해 쓰이는 함수들을 살펴보자. 이 첫번째 함수는 새로운 메뉴바를 만들기 위해 쓰입니다.
GtkWidget *gtk_menu_bar_new()
이것은 이름 그대로 새로운 메뉴바를 만듭니다. 버튼과 마찬가지로, 우리는 이것을 윈도에 패킹하기 위해 gtk_container_add를 이용할수도 있고, 또는 박스에 패킹하기 위해 box_pack 함수들을 이용할 수 있습니다. 즉,  버튼과 같다고 보면 됩니다.

GtkWidget *gtk_menu_new();
이 함수는 새로운 메뉴를 향한 포인터를 리턴하는데, 이것은 실제로 보여지지는 않고(gtk_widget_show를 통해) 다만 메뉴 아이템들을 가지고만 있습니다. 이 아래에 나오는 예제를 보며 더 명확히 이해하기를 바랍니다.

이번의 두 함수는 메뉴나 메뉴바 안으로 패킹되는 메뉴 아이템을 만들기 위해 쓰입니다.
GtkWidget *gtk_menu_item_new()
GtkWidget *gtk_menu_item_new_with_label(const char *label)


이 함수들은 보여지기 위한 메뉴를 만들 때 쓰입니다. gtk_menu_new로써 만들어지는 "메뉴"와 gtk_menu_item_new로써 만들어지는 "메뉴 아이템"을 꼭 구별해야 합니다. 메뉴 아이템은 연결된 동작이 있는 실제의 버튼이 될 것이지만, 반면 메뉴는 이것들을 가지고 있는 컨테이너가 될 것입니다.
gtk_menu_new_with_label과 단순한 gtk_menu_new 함수는 여러분이 버튼에 대해 공부한 후에 짐작하는 그대로입니다. gtk_menu_new_with_label은 라벨이 이미 패킹되어 있는 메뉴 아이템을 만들고, gtk_menu_new는 비어있는 메뉴 아이템을 만듭니다.한번 메뉴 아이템을 만들면 반드시 이를 메뉴 안에 넣어야만 합니다. 이는 gtk_menu_append 함수를 이용해서 이루어집니다. 어떤 아이템이 사용자에 의해 선택되었을 때 이를 알아내어 처리하기 위해서는 activate 시그널을 통상적으로 하듯이 연결합니다. 그래서 만일 Open, Save, Quit 옵션을 가진 표준 File 메뉴를 만들고자 한다면 소스 코드는 다음과 같이 됩니다.


file_menu = gtk_menu_new();    /* 메뉴를 보여줄 필요는 없습니다. */

/* 메뉴 아이템들을 만듭니다. */
open_item = gtk_menu_item_new_with_label("Open");
save_item = gtk_menu_item_new_with_label("Save");
quit_item = gtk_menu_item_new_with_label("Quit");

/* 그것들을 메뉴에 붙입니다. */
gtk_menu_append( GTK_MENU(file_menu), open_item);
gtk_menu_append( GTK_MENU(file_menu), save_item);
gtk_menu_append( GTK_MENU(file_menu), quit_item);

/* "activate" 시그널과 callback 함수를 연결합니다. */
gtk_signal_connect_object( GTK_OBJECT(open_items), "activate",
                   GTK_SIGNAL_FUNC(menuitem_response), (gpointer) "file.open");
gtk_signal_connect_object( GTK_OBJECT(save_items), "activate",
                   GTK_SIGNAL_FUNC(menuitem_response), (gpointer) "file.save");

/* Quit 메뉴 아이템에  exit 함수를 연결합니다. */
gtk_signal_connect_object( GTK_OBJECT(quit_items), "activate",
                   GTK_SIGNAL_FUNC(destroy), (gpointer) "file.quit");

/* 이제 메뉴 아이템들을 보여줘야 합니다. */
gtk_widget_show( open_item );
gtk_widget_show( save_item );
gtk_widget_show( quit_item );


여기까지하면 필요한 메뉴는 일단 만든 것입니다. 이제 지금까지 만든 메뉴를 붙일 File 메뉴 아이템과 메뉴바를 만들어야 합니다. 아이템과 메뉴바를 만든면 아래와 같이 됩니다.

menu_bar = gtk_menu_bar_new();
gtk_container_add( GTK_CONTAINER(window), menu_bar);
gtk_widget_show( menu_bar );

file_item = gtk_menu_item_new_with_label("File");
gtk_widget_show(file_item);


이제 file_item을 메뉴와 연결해야 합니다. 이것은 다음 함수를 통해 이루어집니다.
void gtk_menu_item_set_submenu( GtkMenuItem *menu_item, GtkWidget *submenu);

그래서 우리 예제는 다음 코드로 이어집니다.
gtk_menu_item_set_submenu( GTK_MENU_ITEM(file_item), file_menu);


해야할 남은 모든 일은 메뉴를 메뉴바에 붙이는 일이다. 이는 다음 함수를 이용합니다.
void gtk_menu_bar_append( GtkMenuBar *menu_bar, GtkWidget *menu_item);

우리가 작성한 코드에서는 다음과 같이 됩니다.
gtk_menu_bar_append( GTK_MENU_BAR (menu_bar), file_item );

만일 메뉴들이 help 메뉴가 자주 그러는 것처럼 메뉴바의 오른쪽에 위치하게 하고 싶다면 메뉴바에 메뉴를 붙이기 전에 다음 함수를 쓰면 됩니다. (현재 예제라면 인자로 file_item을 주면 된다.)
void gtk_menu_item_right_justify (GtkMenuItem *menu_item);


메뉴들이 달려있는 메뉴바를 만드는 단계들을 간단히 정리해 보겠습니다. 

gtk_menu_new()를 이용해서 새로운 메뉴를 만듭니다.
gtk_menu_item_new()를 여러번 이용해서 메뉴에 필요한 각각의 메뉴 아이템을 만든다. 그리고 gtk_menu_append()를 이용해서 새 아이템들을 메뉴에 넣습니다.
gtk_menu_item_new()를 사용해서 메뉴 아이템을 하나 만든다. 이 아이템은 자신의 텍스트가 메뉴바 위에 직접 나타나는 root 메뉴 아이템이 됩니다.
gtk_menu_item_set_submenu()를 사용해서 메뉴를 root 메뉴 아이템에 붙입니다.(바로 위 단계에서 만든 메뉴 아이템)
gtk_menu_bar_new()를 이용해서 새로운 메뉴바를 만듭니다. 이 단계는 한 메뉴바 위에 여러 일련의 메뉴를 만들었을 때 한번만 필요합니다.
gtk_menu_bar_append()를 이용해서 메뉴바 위에 root 메뉴를 놓습니다.

팝업메뉴를 만드는 것도 거의 같습니다. 다른 점이 있다면 메뉴는 메뉴바에 의해 자동적으로 붙여지는 것이 아니라, button_press 이벤트로부터 gtk_menu_popup() 함수를 호출함으로써 붙여진다는 것입니다. 이 과정을 따라 설명해보겠습니다.

이벤트 핸들링 함수를 만듭니다. 이것은 아래와 같은 원형을 가져야 합니다.
static gint handler(GtkWidget *widget, GdkEvent *event);
그리고 이것은 메뉴를 팝업시킬 곳을 찾기 위해 이벤트를 이용할 것입니다.
이벤트 핸들러에서는, 만약 이벤트가 마우스 버튼을 누르는 것이라면, 이벤트를 버튼 이벤트로 다루고, gtk_menu_popup()에 정보를 넘겨줍니다.
이 함수를 이용하여 이벤트 핸들러를 widget에 결합시킵니다.
gtk_signal_connect_object(GTK_OBJECT(widget), "event", GTK_SIGNAL_FUNC (handler), GTK_OBJECT(menu));
여기서 widget 인자는 우리가 바인딩할 widget이고, handler 인자는 핸들링 함수입니다. 그리고 menu 인자는 gtk_menu_new()로써 만들어진 메뉴입니다. 예제 코드에서 보인대로, 이것은 메뉴바에 붙여져 있는 메뉴가 될 수도 있습니다.

어때요? 설명이 조금 많아서 어려워 보이지만, 따라해보면 금방 이해할 수 있습니다.
오늘은 Menu에 대한 설명을 하였습니다. 다음주에는 위의 내용을 이용하여 하나의 예제를 해보겠습니다.

 


:
컴퓨터 구조 명령어 사이클
2008. 12. 7. 20:00 :: 컴퓨터 구조

 하루에 2개 올린다는게 정말 쉬운게 아니군요 ㅠ_ㅠ 하지만 열심히 해야한다는 각오로(이번주에도 시험이 2과목...) 블로그를 올리고 있습니다. ㅋㅋ 컴구조를 지금까지 공부하면서 참 간단하다는 생각을 많이 합니다. 복잡한 구조로 움직이는거 같지 않고요 규칙을 따라 동작하는거 같은데 왜이리 수업시간에는 이해하기도 머리에도 들어오지 않던지...뭐 뒤쪽으로 가면 갈수록 더 어려워지나깐요 정신을 차려야겠지요 지난번 블로그에서 아주 간단히 예를 들으면서 한 클럭싸이클 동안에 어떻게 정해저 있는 간단히 봤는데요 이제 부터 본격적으로 한번 보겠습니다.

 컴퓨터에서 각 명령어 사이클은 다음과 같은 단계들로 이루어제 있습니다.
 
 1. 명령어를 메모리에서 가져온다(fetch라고 합니다.)
 2. 명령어를 디코딩한다.
 3. 간접 주소 방식의 명령어일 경우에 메모리로부터 유효 주소를 읽어온다.
 4. 명령어를 실행한다.

 네번째 단계가 끝나면 다시 첫번째 단계로 돌아가 다음 명령어에 대한 fetch, 디코드, 실행 단계를 반복합니다. 이러한 반복은 HALT명령을 만날 때까지 계속하여 반복합니다. 그럼 각 단계에 대해서 알아보도록 하겠습니다.

 Fetch와 디코드 
 
 초기에 프로그램 카운터는 프로그램의 첫 명령어에 대한 주소를 가지고 있으며, 순차 카운터는 0으로 타이밍 변수 T0를 가리킵니다. 다음에 매 클럭마다 타이밍 변수는 T0, T1, T2와 같은 순서로 변합니다. 이 타이밍 변수들에 맞추어서 Fetch와 디코드 단계에 대한 마이크로 연산은 다음과 같은 레지스터 전송문으로 표시 됩니다.


여기서 AR레지스터만이 메모리의 주소 입력에 연결되어 있으므로, T0시간 동안 PC에서 AR로의 데이타 전송이 필요합니다. 메모리에서 읽어온 명령어는 T1에 해당하는 클럭 변이에서 명령어 레지스터(IR)에 저장됩니다. 동시에 다음 명령어의 주소를 위해 PC가 하나 증가됩니다. 시간 T2에서는 IR의 연산 코드부분이 디토드되고, 간접 비트가 플립플롭 I에 전해지며 주소 부분은 AR로 전송이 됩니다.





 위의 그림은 처음 두 레지스터 전송문을 버스 시스템으로 구현한 것입니다. PC에서 RA로의 데이타 경로를 제공하기 위하여 타이밍 신호 T0를 적용시켜 다음과 같은 연결을 형성해야 합니다.

 1. 버스 선택 입력(S2S1S0)DMF 010으로 하여 PC내용이 버스에 놓이도록 한다.
 2. AR의 LD입력을 인에이블 시켜서 버스의 내용을 AR로 전송한다.

 이와 같은 연결이 이루어졌으면 다음 클럭의 변이에서 PC와 AR 사이에 데이터 전송이 일어납니다. 두번째 문장을 구현하기 위해서는 타이밍 신호 T1을 이용하여 다음과 같은 연결을 형성해야 합니다.

 1. 메모리의 읽기 입력을 인에이블시킨다.
 2. S2S1S0=111로 하여 메모리의 내용이 버스에 놓이도록 한다.
 3. IR의 LD입력을 인에이블시켜 버스의 내용에 IR로 전송한다.
 4. PC의 INR입력을 인에이블시켜 PC의 값을 하나 증가시킨다.

 명령어 종류의 결정

 시간 T3동안에 제어 장치는 명령어의 종류를 결정합니다.

 위의 그림에서 보듯이 레지스터 참조 혹은 입출력 명령은 T3에서 수행이 되어 지고 메모리 참조 명령은 T4에서 수행이 되어집니다. 기호로 표시하면 다음과 같습니다.

 D7'IT3 : AR<-M[AR]
 D7'IT3 : 아무런 일도 하지 않는다.
 D7I'T3 : 레지스터 참조 명령어를 수행
 D7IT3 : 입출력 명열어를 수행



레지스터 참조 명령어

 레지스터 참조 명령어는 D7=1 이고 I=0 인 명령어로 IR(0-11)에 있는 나머지 12비트로 12가지 명령어를 나타냅니다. 모든 제어 함수는 D7I'T3의 부울식이 필요한데 이것을 간단히 기호 r로 나타내며, IR(0-11)레지스터의 각 비트를 Bi로 표시하여 각 명령어에 대한 제어 함수를 구별합니다. 예를 들어 16진 코드로 7800인 명령어 CLA는 이진 코드로 0111 1000 0000 0000 을 가리키기 때문에 I', D7, B11들이 1의 값을 가집니다. 따라서 이 명령어에 대한 마이크로 연산을 구동시키는 시간 제어 함수는 D7I'T3B11=rB11이 됩니다. 이와 같이 레지스터 참조 명령어는 사간 T3에 수행이 완료되고, 순차 카운터의 타이밍 신호는 다시 T0으로 돌아갑니다.

 처음 7개의 명령어는 AC나 E레지스터에 대한 마이크로 연산을 나타내며 다음의 네 명령어는 주어진 조건이 만족될 때 다음 명령어를 수행하기 위해  PC를 다시 한번 증가시키는 연산을 나타냅니다. 마지막으로 HLT명령은 시작-끝 플립플롭 S를 클리어하고 순차 카운터의 동작을 멈추게 합니다.

다음 블로그에서는 메모리 참조 명령어에 대해서 알아보도록 할게요 그럼 시험기간 모드들 시험 잘보세요^^


:
컴퓨터 구조 타이밍과 제어 이야기
2008. 12. 7. 16:59 :: 컴퓨터 구조
안녕하세요 시그원 여러분 어느덧 12월 달이군요 눈도 2번이나 오고 요즘 따라 마음이 싱숭생숭하답니다. 아무튼 지난주에 시험기간이였기에 부득이하게 블로그를 올리지 못했습니다. but 벌금을 내야한다는 사실 ㄷㄷㄷ 미리미리 많이 많이 올려야 하는데 제 게으림을 탓할수 밖에 없는 현실입니다. 

 지난 블로그에서는 컴퓨터 명령어에 대해서 알아보았습니다. 그 내용이 무척 중요하죠 일단 명령어와 명령어의 내용을 정확히 알지 못한다면 시험은 손도 못댄다고 봐야죠 주로 많이 사용하는 명령어들이 메모리 명령어들은 다 중요하고요 레지스터리 명령어는 CLA, CLE, CMA, CME 생각해보니깐 다 중요하네요...아무튼 그럼 본격적으로 타이밍과 제어부분에 대해서 설명해 보겠습니다.

 기본 컴퓨터의 모든 플립플롭과 레지스터는 주 클럭 발생기에 의하여 제어됩니다. 그러나 클럭 펄스만으로는 레지스터의 상태를 변경시킬 수 없고, 제어 장치에서 생성된 제어 신호가 인에이블시켜 주어야 합니다. 제어 장치는 하드와이어(hardwired)제어 방시과 마이크로 프로그램(microprogrammed)제어 방식의 두 종류가 있습니다.  하드웨어 방식은 게이트, 플립플롭, 디코더 등의 디지탈 회로를 이용하여 제어 논리를 구현하기 때문에 속도면에서 유리하지만 컴퓨터의 구조가 변경되었을 때 여러 부품들 사이의 배선까지 바꾸어 주어야 하는 단점이 있습니다 반면에 마이크로 연산을 순차적으로 수행시키기 때문에 설계가 변경되더라도 제어 메모리의 마이크로 프로그램만 갱신해주면 됩니다.
 위의 그림은 제어 장치의 블럭도인데 이것은 구 개의 디코더와 하나의 순차 카운터, 그리고 여러개의 제ㅐ어 논리 게이트로 구성되어 있습니다. 메모리에서 읽어온 명령어는 공통 버스 시스템에 있는 명령어레지스터(IR)에 놓이게 되고, 이 중에서 연산 코드 부분이 3x8디코더에 의해 D0~D7까지로 디코딩됩니다. 명령어 레지스터의 5비트는 I로 표시되는 플립플롭에 전송되며, 나머지 0에서 11번째 비트들은 제어 논리 게이트로 연결이 됩니다. 4비트 순차 카운터(SC)의 출력은 디코더에 의해 T0~T15까지 16개의 타이밍 신호(이게 제어신호이죠)를 생성합니다.

 순차 카운터는 동기적으로 클리어되는 기능을 가지고 있고 예를 들어 타이밍 신호가 T0, T1,T2,T3,T4와 같은 순차로 카운트된다고 가정하면 시간 T4에서 디코더가 출력 D3가 활성화되었을 때 SC가 0으로 클리어되도록 하는 문장을 D3T4 : SC<-0 라고 씁니다 아! 여기서 SC는 동기적으로 클리어 되는 기능을 가짐니다. 그럼 계속해서 D3T4 : SC<-0 에 대한 제어 신호의 시간 관계를 보여주는 타이밍도를 보겠습니다.
 처음에  SC의 CLR입력이 1이므로, 첫번째 클럭의 상승 변이에서 SC가 0으로 클리어되고 이것은 타이밍 신호  T0를 만듭니다. 다음에 매 틀럭마다 SC가 증가되어  T1에서 T4까지 타이밍 순서를 생성합니다. 위의 그림에서 마지막 세 개의 타이밍 파형에서 보는 바와 같이 시간 T2에서 연산 코드 디코더의 출력 D3가 1로 활성화 됩니다. 그리고  T4가 1로 되었을 때 SC의  CLR입력에 연결되는 D3T4의 값도 1이  됩니다. 따라서 다음 클럭의 상승 변이가 일어나기 전에 끝마쳐지게 된다. 그러나 많은 컴퓨터에서 메모리 사이클은 프로세서의 클럭 사이클보다 더 길기 때문에 이러한 타이밍 관계는 실제로 맞지 않습다. 즉 이 경우에 프로세서는 메모리 워드가 유효해질 때까지 몇 사이클을 기다리고 있어야 합니다. 컴퓨터의 동작을 완전히 이해하려면 클럭 변이와 타이밍 신호 사이의 시간 관계를 잘 알아야 합니다. 예를 들어 T0 : AR<-PC 레지스터 전송문은 타이밍 신호 T0가 1일때 PC의 값을 AR로 전송하는 것을 나타냅니다. 이 경우에 T0는 한 클럭 사이클 동안 1을 유지하는데, 이 기간 동안 PC의 내용이 버스에 올려지고(S2S1S0=010) AR의 LD입력도 인에이블 됩니다. 그리고 실제 데이타의 전송은 다음 클럭의 상승 변이에서 일어납니다. 이와 동시에 순차 카운터 SC의 값이 0000D에서 0001로 하나 증가하여 다시 한 클럭 사이클동안 T1이 1로 됩니다.  다음 블로그에서 명령어 사이클에 대해서 자세히 알아보도록 하겠습니다.

:
Indentation & Blank space
2008. 12. 6. 00:28 :: Code Convention

1. Indentation (들여쓰기)
 
- Indentation 은 Tab 키를 사용한다.

- Tab size 는 4나 8로 정한다.

- 복합문이 중첩된 경우 포함될 내용은 복합문장의 Tab위치보다 한 Tab만큼 오른쪽으로 띄워 기록한다.

- ‘ { ‘ 기호와 ‘ } ’ 기호는 같은 indentation을 가지며, 그 줄에는 어떠한 code도 위치할 수 없다.(Comment제외)
     단, { } 사이에 들어갈 내용이 한줄에 적힐 정도로 충분히 적을 경우에는 동일한 줄에 위치할 수 있다.

 Good  Bad
 struct boat
{
    int wllength;
    BoatType type;
    long sailArea;
};		  struct boat {
int wllength;
BoatType type;
long sailArea;
};



2. Blank space

-  Keyword (if, while, return, switch, for등) 와 ‘(‘사이에 한 칸을 띄운다.
    그러나 functio, sizeof, macro 의 경우에는 붙여준다.
ex) if ( ((a + b) / (c + d)) == 0 )

- paranthesis '('과 ')' 안에 들어가는 문자, 숫자의 길이가 짧을 경우 paranthesis와 붙여쓰고, 그렇지 않을 경우 한칸띄어준다. 

-  ‘,’ 뒤에 새로운 줄이 시작되지 않는 경우, 다음 항목과 한 칸을 띄운다.

- Binary operator의 경우 operator의 양쪽에 한 칸을 띄운다. (주의: ->, ., [] operator는칸을 띄우지 않는다.)

- Unary operator의 경우 operator와 operand 사이를 붙인다.

- ( )가 nesting되어 나타나는 경우, 최대한 readability를 고려하여, 빈 칸을 띄운다.







:
알고리즘 코딩기법 - 7. Bit 연산 Brute Force
2008. 12. 4. 22:00 :: 알고리즘코딩기법
안녕하세요 조일룡입니다.

이번에는 2진수를 이용하여 모든 경우의 수를 탐색하는 Brute Force에 대해 알아보겠습니다.


Brute Force

Brute Force는 문제를 해결할 수 있을지도 모를 모든 후보 해를 전부다 탐색하여 정말로 문제를 풀 수 있는 해를 찾는 방법입니다. 쉽게 생각해서 문제가 1 + x = 100 인 경우 이 문제의 해 x가 [0, 100] 사이의 자연수라는 것을 안다고 가정했을 때 단순히 x에 0부터 100까지 모두 대입해 보고 문제가 풀리는 x값을 찾는식의 방법입니다. 물론 저 문제를 저렇게 푸는 바보는 없어야 하겠죠?

여튼 위의 '예' 처럼 Brute Force는 해법이 간단하고 쉬운 반면 모든 후보해를 탐색해야하기 때문에 상당히 느리다라는 단점이 있습니다. 그럼에도 Brute Force를 간간히 사용하는 이유는 쉽기 때문이죠.. 그리고 모든 경우를 따지지 않고서는 도저히 해를 찾지 못하는 문제도 존재합니다.


Basic Algorithm

Brute Force를 구현하는 기본 골격을 살펴보겠습니다.
    1. first (P): generate a first candidate solution for P.
    2. next (P, c): generate the next candidate for P after the current one c.
    3. valid (P, c): check whether candidate c is a solution for P.
    4. output (P, c): use the solution c of P as appropriate to the application

    c \gets first(P)
    while c \neq Λ do
      if valid(P,c) then output(P, c)
      c \gets next(P,c)


Combinatorial explosion

안타깝게도 Brute Force는 입력크기가 커지면 사용하지 못하는 경우가 많습니다. (느리기 때문이지요)

최악의 경우

100 명의 사람들을 최적의 순으로 줄을 세우는 경우를 생각해봅시다. (어떤 경우가 최적인지는 일단 논외로 하겠습니다) 이런 문제에선 모든 경우가 몇 가지나 될까요... 100명의 사람을 순서대로 줄을 세운다.... 고등학교 때 배운 기억이... 나시나요??
기억을 더듬어보니 수학책에서 n 개의 사탕 중 r개를 순서대로 선택하는 경우의 수 nPr = n! / (n-r)! 을 본 적 있는것 같습니다.
100명의 사람중 100명을 순서대로 줄 세우는 경우의 수 = 100 P 100 = 100! / (100-100)! = 100! 이네요!!!!

경우의 수가 이처럼 팩토리얼로 나오면 입력크기가 10이 넘어가면 일반 PC로는 시간이 기하급수적으로 느려집니다. 참고로 10! = 3,628,800 입니다. 정말 참을성이 대단하더라도 입력크기가 15가 되면 15! = 1,307,674,368,000 가 되어 며칠동안 눈뜨고 기다려야 답을 볼 수 있습니다... 흠... 몇년이 될지도 모르겠네요


다른 경우를 생각해봅시다.

당신은 로또를 좋아합니다. 어디선가 잡지를 보니 로또 번호 조합에 따른 당첨 확률 계산공식이 나와 있습니다. 당신은 모든 로또 조합의 경우의 수 중 최고의 당첨 확률을 가지는 번호를 고르고 싶습니다. 한번 Brute Force로 풀어봅시다.
역시 모든 경우의 수를 따져야 하겠습니다. 로또는 45개 숫자 중 6개를 선택하죠.. 맞나요? 다시 고등학교 수학시간으로 돌아가서 n개의 사탕 중 r개를 순서에 상관없이 고르는 경우의 수는.... nCr = n! / ((n-r)! * r!) 이었군요..
45개의 숫자 중 6개를 고르는 경우의 수는 45 C 6 = (45 * 44 * 43 * 42 * 41 * 40) / (6 * 5 * 4 * 3 * 2 * 1) = 8,145,060 이네요..
뭐 이정도는 그나마 PC로 돌릴만 하겠군요....

경우의 수가 조합(Combination)으로 나오면 계산기로 간단히 계산을 해보고 이게 해뜨기전(?!)에 답을 볼 수 있는지 확인한 후 코딩을 시작해야겠습니다.


비트를 사용할 수 있고 가장 빈번히 발생하는 2^n의 경우

당신은 겁나먼 왕국의 대마법사입니다. 어느날 슈렉의 외모에 질려버린 피오나 공주가 당신에게 마법을 부려 슈렉의 외모를 바꾸고 싶어합니다. 당신은 외모를 바꾸는 n가지 마법을 가지고 있고 i번째 마법은 슈렉의 외모를 score(i)만큼 변화 시킬 것입니다. (score(i)는 음수일 수도 있습니다!!) 각 마법은 서로 독립적으로 작용하고 같은 마법을 두 번 이상 쓰더라도 점수는 한 번만 적용됩니다. 슈렉의 현재 외모 점수는 0점이고 피오나 공주는 슈렉의 외모가 정확히 S점이 되기를 원합니다. 당신은 어떤 마법을 쓰겠습니까??

이런경우 n가지의 마법을 놓고 어떤 마법을 쓰고 어떤 마법을 쓰지 않을지를 결정을 해야하겠습니다. 몇 개의 마법을 쓰는지는 자유이기 때문에 모든 경우의 수는 nC0 + nC1 + nC2 + ... + nCn = 2^n 입니다. 더 쉽게 생각하면 각각의 마법마다 쓰는 경우와 안 쓰는 경우 2가지 선택을 할 수 있는데, 마법이 n개 이므로 모두 곱하면 2^n의 경우의 수가 나옵니다.

바로 이런경우 bit연산을 이용하여 쉽게 문제를 해결할 수 있습니다.

2^20 = 약 100만 이고 2^30은 10억 입니다. PC에서 돌린다고 생각해 봤을 때 이 처럼 경우의 수가 2^n이 나오는 경우 n이 30이 넘어가면 밤샐준비를 해야 하겠습니다. (물론 밤은 PC가 새겠군요;)



Brute Force! Bit 조작해서 풀기

다른 예를 생각할 필요없이 아까전에 피오나가 낸 문제를 가지고 해보겠습니다.

당신이 부릴수 있는 마법이 20개라고 합시다. 그리고 각각의 마법에 따른 용모의 변화가 벡터 score로 넘어옵니다. 마법의 점수 합이 S가 되는 모든 경우에 대해 사용하는 마법의 번호(0~19)를 오름차순으로 출력하는 함수를 작성하겠습니다.
view plaincopy to clipboardprint?
  1. //////////////////////////////////////////////////////////////////////   
  2. //   
  3. //  void Magic(vector<int> socre, int S)   
  4. //  슈렉의 외모를 S로 만드는 마법의 조합을 찾는다   
  5. //   
  6. //  vector<int> score : i번째 마법이 슈렉의 외모점수를 socre[i]만큼 변화시킨다   
  7. //  int S : 피오나가 원하는 슈렉의 외모 점수   
  8. //   
  9. void Magic(vector<int> score, int S)   
  10. {   
  11.     int i = 0, j = 0;   
  12.     int n = score.size(); // 마법의 갯수   
  13.   
  14.     // 모든 경우(2^n)를 탐색   
  15.     for (i = 0; i < (1 << n); i++)    
  16.     {   
  17.         // 사용하는 마법의 점수 합   
  18.         int sum = 0;   
  19.   
  20.         // 모든 마법 탐색   
  21.         for (j = 0; j < n; j++)    
  22.         {      
  23.             // i의 경우 j번째 마법을 사용 하는가?   
  24.             if (i & (1 << j))    
  25.             {   
  26.                 // j번째 사용한다면 점수는 score[j]만큼 변한다.   
  27.                 sum += score[j];   
  28.             }   
  29.         }   
  30.            
  31.         // 사용한 마법의 점수 합이 S이면 마법 출력   
  32.         if (sum == S)   
  33.         {   
  34.             // 모든 마법 탐색   
  35.             for (j = 0; j < n; j++)    
  36.             {   
  37.                 // j번째 마법을 사용했으면 출력   
  38.                 if (i & (1 << j))   
  39.                 {   
  40.                     cout << j << " ";   
  41.                 }   
  42.             }   
  43.             cout << endl;   
  44.         }   
  45.     }   
  46. }  



같은 문제를 DFS로 구현하는 백트레킹(backtracking)으로도 풀 수 있습니다.
view plaincopy to clipboardprint?
  1. //////////////////////////////////////////////////////////////////////   
  2. //   
  3. //  void MagicBacktrack(vector<int>& score, int S, int index, int use)   
  4. //  슈렉의 외모를 S로 만드는 마법의 조합을 찾는다(백트레킹)   
  5. //   
  6. //  vector<int>& score : i번째 마법이 슈렉의 외모점수를 socre[i]만큼 변화시킨다   
  7. //  int S : 피오나가 원하는 슈렉의 외모 점수   
  8. //  int index : index 번째의 마법을 사용할지 안할지를 검사함   
  9. //  int use : use의 i번째 bit가 1이면 i번째 마법을 사용하기로 결정함   
  10. //  int sum : 사용하기로 한 마법의 점수 합   
  11. //   
  12. void MagicBacktrack(vector<int>& score, int S, int index, int use, int sum)   
  13. {   
  14.     // 마법의 수   
  15.     int n = score.size();   
  16.   
  17.     // 모든 마법에 대해 선택 여부를 결정했음   
  18.     if (index == n)    
  19.     {   
  20.         // 선택한 마법의 합이 S -> 선택한 마법을 출력   
  21.         if (sum == S)   
  22.         {   
  23.             // n개의 마법을 탐샙   
  24.             for (int i = 0; i < n; i++)    
  25.             {   
  26.                 // i번째 마법을 사용하기로 했네요   
  27.                 if (use & (1 << i))    
  28.                 {   
  29.                     cout << i << " ";   
  30.                 }   
  31.             }   
  32.             cout << endl;   
  33.         }   
  34.         return;   
  35.     }   
  36.   
  37.     /* 마법점수가 양수만 존재한다면 아래 가지치기로 탐색범위를 줄일 수 있다.  
  38.     if (sum > S)  
  39.     {  
  40.         return;  
  41.     }  
  42.     */  
  43.   
  44.     // index 번째 마법을 사용하기로 결정함   
  45.     MagicBacktrack(score, S, index + 1, use | (1 << index), sum + score[index]);   
  46.   
  47.     // index 번째 마법을 사용 안하기로 결정함   
  48.     MagicBacktrack(score, S, index + 1, use, sum);   
  49. }   
  50.   
  51. int main()   
  52. {   
  53.     // 함수가 잘 도나 테스트 해보는 코드입니다.   
  54.     vector<int> score;   
  55.   
  56.     score.push_back(15);   
  57.     score.push_back(13);   
  58.     score.push_back(-5);   
  59.     score.push_back(7);   
  60.     score.push_back(55);   
  61.     score.push_back(12);   
  62.     score.push_back(3);   
  63.     score.push_back(1);   
  64.     score.push_back(-11);   
  65.     score.push_back(-6);   
  66.     score.push_back(4);   
  67.   
  68.     MagicBacktrack(score, 47, 0, 0, 0);   
  69. }  



DFS의 기본은 알고리즘 코딩기법 - 3. 재귀호출을 참고하시면 됩니다. 백트레킹에 대해서는 혹시나 마음이 내키면 포스팅 하겠습니다.

저작자표시 동일조건

:
Verilog HDL 2. 문법
2008. 12. 3. 12:00 :: FPGA
이번에는 Verilog HDL의 문법에 대해서 알아보겠습니다.
각각의 Programming Language 마다 정해진 문법이 있듯이 Verilog HDL도 정해진 규칙이 있습니다. C Language와 크게 다른 것은 없지만 어느면에서 틀리고 어떤 특징을 가지고 있는지 알아보겠습니다.

1. 기본적인 사항
- 여백(white space) : 빈칸(space), 탭(tap), carriage return, line feeds 등 사용
                               단어들을 분리하는데 사용
                               공백(blank), tap 은 문자열에서 의미 있게 취급된다.
- 이름 or 식별자(identifiers)등으로 사용되는 문자는 소문자와 대문자를 구별. 예약어는 반드시 소문자로 기술하여야 한다.
- 한 문장은 반드시 세미콜론(;)으로 끝난다. (end~ 로 시작되는 예약어는 제외)

2. 주석(comments)
- C Language와 비슷하게 사용
- 소스 코드의 설명을 위해 사용. 컴파일 과정에서 무시됨
- 단일 라인 주석문 : 2개의 슬래쉬 (//) 로 시작되어 해당 라인의 끝까지가 주석이 된다.
- 블록 주석문 : /* ~~~ */ 로 표시 여러줄에 걸쳐서 주석을 사용할 수 있다.

3. 수 표현 (number representation)
정수형(integer)
<비트폭>'(따옴표로 분리)<진수><값>
- 비트폭이 없는 경우 32비트 10진수를 나타낸다.
- 진수 표현 법
 b, B : 2진수
 o, O : 8진수
 d, D : 10진수
 h, H : 16진수
- 진수에 대응 되는 값
 2진수 : 0, 1, x, z
 8진수 : 0~7, x, z
 10진수 : 0~9(x, z 사용 불가)
 16진수 : 0~9, a~f(A~F), x, z

ex) 1'b1 -> 1비트폭을 가지는 2진수. 값은 1
     8'o377 -> 8비트폭을 가지는 8진수. 값은 11111111

- 숫자에서 언더바(_)를 사용하여 읽기 쉽게 할 수 있고, 숫자 크기에 영향을 주지 않는다.

실수형(real)
<가수><E or e><지수>
- 가수 : 10진수

ex) 32e-4 -> 0.0032
      4.1E3 -> 4100

4. 문자열(string)
- 겹따옴표(" ") 사이에 있는 문자들. 단일 라인에 존재해야 한다. 여러 라인에 걸친 문자열은 사용 불가
- 8비트 ASCII값으로 표현되는 unsigned 정수형 상수로 취급
- 문자열 변수는 reg형 변수이며, 문자열 내의 문자 수에 8을 곱한 크기의 비트 폭을 가진다.

ex)
reg [8*12:1] string_var;
initial begin
    string_var = "Hello world!";
end

- 특수 문자 앞에 확장 문자를 사용하면 일부 특수 문자를 문자열에 포함시킬수 있음.
\n, \t,  \\, \", %%
- 스트링은 시뮬레이션에만 사용된다.

5. 식별자(identifiers)
- 식별자는 사용자가 정의한 변수, 모듈 이름, 포트 이름, 함수 이름, 인스턴스 이름 등을 말한다.
- 대소문자를 구별하여 인식
- 가독성을 위해 언더바(_) 사용 가능
- 단순 식별자 : 문자, 숫자, 기호 $, 언더바 등으로 구성
                      첫번째 문자는 숫자나 기호 $ 사용 불가, 문자 또는 언더바만 사용
- 확장 식별자(escaped identifier) : back slash 로 시작 되며 여백(빈칸, 탭, 줄바꿈) 등으로 끝남
                      프린트 가능한 ASCII 문자들을 식별자에 포함시키는 수단을 제공
ex) \***error***
       \{a,b}

6. 키워드(keyword)
- Verilog HDL 구성요소를 정의하기 위해 미리 정의된 식별자(예약어)
- 확장문자가 포함된 키워드는 키워드로 인식되지 않는다.


이상으로 간단하게 문법을 알아 보았습니다.
다음시간엔 실제로 QUATUS를 사용하여 Verilog HDL로 여러가지 로직설계하는 방법과 시뮬레이션 방법을 알아가 보도록 하겠습니다.

:
VPL 기본 4. if 조건문, switch 조건문 처리.
2008. 12. 2. 22:00 :: MSRDS

3주만에 글 쓰는군요...0ㅁ0;;

허을...

-ㅁ-aaa

아 그리고 MSRDS 2008최종버전이 나왔더라구요.

다운로드 링크는 아래로~

http://www.microsoft.com/downloads/details.aspx?familyid=84c5b49f-0f9c-4182-a267-a951328d3fbd&displaylang=en#filelist


이번 시간은 if문 사용해보도록 하겠습니다.

음...

두가지 값을 입력 받아서 그 값들이 같은지. 다른지 확인하여 출력해 주는 프로그램을 만들어 보겠습니다.

먼저 SimpleDialog activity 두 개와 Calculate Activity 두 개를 추가하여줍니다.

각 각 하나씩 연결하여 주시고. PromptDialog - Success 를 선택하여 줍니다.



그리고 그 두개를 연결한 Join Activity를 추가하고 연결하여 줍니다.


그리고 If Acvity와 Data Activity를 추가하고, Join Activity와 If Activity를 연결하여 주시고, If의 조건은 두 값을 같은지 다른지 비교하는 것이므로,  msg == msg0 이라는 문을 추가하여줍니다.
그 If Activity와 Data Activity를 참 일때와 거짓일때 각각 연결하여주시고, 참인 Data Activity에는 같다 라는 문장을 적어주시고 string 형으로 선언하여 줍니다. 거짓인 Data Activity에는 다르다 라는 문장을 적으시고 string를 선택하여줍니다.


이제 그 Data들을 각각 표시할 Dialog를 추가하여줍니다.

Data Activity와 SimpleDialog를 연결하시고, AlertDialog를 선택하시고,


Data Connections에서는 value를 선택합니다.


그러면 오늘 실행해볼 프로그램은 다 끝났구요. 다하면 다음과 같은 모습을 갖게 됩니다.


실행을 시켜보면~

Prompt Dialog 창이 두개 뜨구요. 거기에 각각 원하는 문장이라던지 적으시고, OK를 하시면

같으면 같다 라는 Alert Dialog, 다르면 다르다 라는 Alert Dialog를 보실수 있습니다.


그리고 Switch 조건문 처리에 관한 예제 인데요.


위 그림과 같이 구성하시면 됩니다.

Prompt Dialog로 입력받은 문자열을 switch문에서 찾아서 해당하는 것을 따라 Data가 출력됩니다.

오늘 새로본 Activity가 두 가지가 더 있는데요.

merge와 join 인데, 그 둘의 차이점은 merge 같은 경우는 연결되어있는 입력점의 값들이 하나라도 입력되면 해당 출력점으로 전달을 하여주고, join 같은 경우는 모든 값들이 다 입력되야 해당 출력으로 전달을 합니다.

:
prev 1 2 3 4 5 ··· 11 next
:: total
:: today | :: yesterday
Designed by arisnoba
다솜돌이's Blog is powered by Daum

티스토리툴바