블로그가 뭔가염? 먹는건가염? 우걱우걱

먼저 새 프로젝트를 생성합니다.



상단의 입력 폼에는 프로젝트의 이름을 적습니다.
하단에는 include 할 헤더 파일들을 어디서 가져올 것인지를 정하는 것인데, browse를 클릭합시다.


win avr 이 설치된 디렉터리로 가서 avr/include 디렉토리를 선택해 줍니다. (만약, 다른 컴파일러용 프로젝트를 생성한다면 해당 컴파일러의 include 디렉토리를 선택해주면 됩니다.)

그러면, 새 프로젝트 설정창이 나옵니다.


프로젝트에 사용될 소스 파일이 있는 디렉토리를 선택해 줍니다.

그러면 다음과 같은 화면이 나오고, 이제 프로젝트에 참조할 include 파일들을 실제로 추가 시켜주는 작업이 남았습니다.


include 디렉토리를 선택하고 Add All을 선택합니다.


위와 같은 화면이 나오는데 첫번째 것을 선택하면 하위 디렉토리의 파일도 같이 포함시킨다는 것이고, 그 아래 것은 하위의 모든 하위까지 포함시킨다는 것인데, 이것을 선택하면 다른 칩들의 헤더파일까지 모두 포함시켜버리므로 두개의 체크를 풀어줍시다.



이제 하위 디렉토리를 포함시켜 줘야 하는데 Compat과 Util 디렉토리는 칩과는 상관없이 공통으로 필요한 헤더들이므로 모두 포함시켜 줍시다.



Avr 디렉토리에서는 위쪽의 Io1200.h 앞의 파일까지와 아래쪽 Iox64a3.h 아래쪽 파일들 역시 칩과 관계없이 공통으로 필요한 헤더들이므로 더블 클릭이나 Add 버튼으로 포함시켜 줍니다.


이제 사용하는 칩의 헤더파일을 포함시켜주면 끝입니다. ATmega128용 프로그램을 작성한다면, Iom128.h를 포함시켜주고 Close를 클릭합니다.

이제 프로젝트에 포함된 헤더파일들을 실제 소스에서 참조 할 수 있도록 동기화를 시켜 주어야 합니다.

Project - Synchronize Files 를 선택해 줍니다.



첫번째 것을 체크하게 되면 좀전에 디렉토리에는 있지만 포함시키지 않은 파일들이 다시 포함되어버립니다. 따라서 체크를 해제 해주고 두번째 것만 채크해 주면 동기화를 시작하고 프로젝트를 시작할 준비가 모두 끝납니다.


이제 소스에서 매크로 함수나 define 값등을 ctrl 을 누른 상태로 클릭하게 되면 해당 헤더 파일로 링크를 시켜줍니다. 다만 이것은 소스 인사이트 내에서 보여주는 것일 뿐이고 실제로 컴파일 할때는 소스에서 직접 include를 시켜줘야 참조하게 됩니다.

SPI는 Serial Peripheral Interface의 약자로 시리얼 방식의 주변장치를 위한 인터페이스로 모토로라에서 제창된 통신 방식이다. 단순하고 범용적이기 때문에 많이 사용되고 있다.

SPI는 기본적으로 세가닥의 선이 필요하고(Clock, Data in, Data out), Chip select까지 있다면 4선이 필요로 한다.
칩의 개수만큼 Chip select 선이 필요하므로 칩의 개수가 적을 때 유용하며, TWI보다 구성이 훨씬 간단하여 TWI보다 무려 20배의 속도를 낼 수 있다고 한다.

atmega128에서 spi 통신을 시작하기전 관련 레지스터를 초기화 함수를 구현하였다.


// SPI Registers #define SPCR (*(volatile unsigned char*) 0x2D) #define SPSR (*(volatile unsigned char*) 0x2E) #define SPDR (*(volatile unsigned char*) 0x2F) // SPCR register bit define #define SPR0 0 #define SPR1 1 #define CPHA 2 #define CPOL 3 #define MSTR 4 #define DORD 5 #define SPE 6 #define SPIE 7 // SPSR register bit define #define SPI2X 0 #define WCOL 6 #define SPIF 7
void SPI_Init(void) { // Double speed SPI Clock // SPR2 = 1 sbi(SPSR, SPI2X); // Set Master Mode sbi(SPCR, MSTR); // Clock Polarity : Idle Low cbi(SPCR, CPOL); // Clock Phase : Leading cbi(SPCR, CPHA); // Set Clock : Fosc/2 // SPR1 = 0, SPR0 = 0 cbi(SPCR, SPR1); cbi(SPCR, SPR0); // SPI 활성화 sbi(SPCR, SPE); return; }

struct pcap {
    int fd;
    int snapshot;
    int linktype;
    int tzoff;              /* timezone offset */
    int offset;             /* offset for proper alignment */
   
    struct pcap_sf sf; /* save file 관련 구조체 */
    struct pcap_md md; /* 패킷의 상태에 대한 정보 */
   
                       /*
                       * Read buffer.
    */
    int bufsize;
    u_char *buffer;
    u_char *bp;
    int cc;
   
    /*
    * Place holder for pcap_next().
    */
    u_char *pkt;
   
   
    /*
    * Placeholder for filter code if bpf not in kernel.
    */
    struct bpf_program fcode;
   
    char errbuf[PCAP_ERRBUF_SIZE];
};

typedef struct pcap pcap_t;
=======================================================================================================

Each packet in the dump file is prepended with this generic header.
This gets around the problem of different headers for different
packet interfaces.

struct pcap_pkthdr {
    struct timeval ts;      /* time stamp */
    bpf_u_int32 caplen;  /* length of portion present */
    bpf_u_int32 len;       /* length this packet (off wire) */
};

=======================================================================================================

문자열은 30자로 제한

교체할 문자는 10자로 제한한다고 가정


#include <stdio.h> #include <string.h> char * change_word(char *string, char *old_word, char *new_word); int main() { char string[30]; char old_word[10]; char new_word[10]; printf("Input string: "); fgets(string, sizeof(string), stdin); printf("Input old word: "); scanf("%s", old_word); printf("Input new word: "); scanf("%s", new_word); strcpy(string, change_word(string, old_word, new_word)); printf("change string: %s\n", string); return 0; } char * change_word(char *string, char *old_word, char *new_word) { char *token; char temp[30]; memset(temp, 0, sizeof(temp)); token = strtok(string, " "); while(token != NULL) { if(0 == strcmp(token, old_word)) { strcat(temp, new_word); } else { strcat(temp, token); } strcat(temp, " "); token = strtok(NULL, " "); } temp[strlen(temp)-1] = 0; return temp; }

실행화면

오늘은 무손실 압축의 대표적인 알고리즘인 허프만 알고리즘에 대해서 알아보겠습니다.

허프만 부호화, 허프만 압축, 허프만 알고리즘등으로 불리우는 이 알고리즘은 문자들의 빈도수에 따라 서로 다른 길이의 부호를 부여하여 압축하는 방식으로, 1952년 당시 박사과정 학생이던 데이비드 허프만이 A Method for the Construction of Minimum-Redundancy Codes란 제목의 논문으로 처음 발표했습니다.

허프만 알고리즘은 JPEG이나 MPEG 같은 영상처리에서 많이 사용되고 있으며 우리가 많이 쓰는 알집 역시 허프만 알고리즘으로 한번 압축을 한 다음에 Lempel 이라는 알고리즘으로 압축을 합니다.

허프만 알고리즘은 그렇게 어렵지 않은 알고리즘이면서도 꽤 괜찮은 압축율을 보입니다.

이번 포스팅에서는 허프만 알고리즘의 원리와 절차에 대해서 알아보고 다음 포스팅 쯤에서 실제로 구현해보도록 하겠습니다.



=======================================================================================================

허프만 부호화로 위키에서 검색을 해보면 간략한 설명과 함께 아래와 같은 간략한 절차가 나와있습니다.


문서를 허프만 알고리즘으로 압축하기 위해서는 먼저 문서안에 포함된 문자들의 빈도수를 조사하여 정렬하는 절차가 필요합니다.

만약 다음과 같은 데이터가 있다고 한다면 다음과 같은 빈도수를 줄 수 있습니다.

데이터: ACABFEAFDE

데이터	빈도수	등장확률(가중치)
A	3	0.3
B	1	0.1
C	1	0.1
D	1	0.1
E	2	0.2
F	2	0.2

위의 결과를 빈도수에 따라 오름차순으로 정렬을 합니다.




이제 이 값들을 이용하여 이진트리를 생성합니다.

먼저 가장 작은 빈도수의 값을 두개 선택해서 리프노드를 두개 만들고 두 노드의 가중치를 더해서 부모노드를 만듭니다. 그리고 정렬된 리스트에서 선택된 두개의 노드를 삭제하고 부모노드를 추가 시킵니다.

 




위의 과정을 리스트에 노드가 1.0 하나만 남을 때까지 반복합니다. (모든 빈도수 확률을 더하면 1.0이 되기 때문에)

위의 소스를 모르는 사람은 없을 것이다.

하지만 다음과 같은 소스가 가능할까?


객체를 객체끼리 더해서 대입한다...라는 뜻인거 같은데 가능해보이지는 않는다.


물론 가능하지 않다.

하지만 C++에서는 가능하도록 만들 수 있다.
바로 연산자 오버로딩을 이용해서 연산자를 재정의하면 위의 코드가 가능해지도록 만들 수 있다.


더하기 연산자를 다시 한번 자세히 살펴보도록 하자.

a = 1 + 2;
라는 코드가 있다고 한다면, 이 코드를 자세히 보면 연산자 우선 순위에 의해서 +가 먼저 실행되고, =가 그 뒤에 실행되는데, + 를 보면 + 를 기준으로 앞 뒤의 정수들 더해서 정수를 만들어 준다는 것을 알 수 있다.

이를 바꿔 말하면, 두 개의 정수형 인자를 받아서 한개의 정수를 리턴해준다고도 표현할 수 있을 것이다. 마치 함수와 같이 말이다.

이것을 함수로 나타낸다면 int 더하기(int, int) 이런식으로 표현할 수 있을 것이다.

C++에서는 함수를 오버로딩(재정의)할 수 있는데 마찬가지로 연산자 또한 재정의를 할 수 있다. 따라서 이 + 를 재정의해서 객체와 객체를 어떤 조건으로 더하고 다시 객체를 리턴해주는 식으로 만들어 준다면 객체끼리의 덧셈도 가능하게 만들 수 있을 것이다.

다만, 연산자를 재정의할 때는 함수와 구별하기 위해 operator라는 예약어를 사용한다.

사용법은 다음과 같다.



실제로 사용한 소스는 아래와 같다.


operator+를 구현한 부분을 보면 인자를 하나로 받아서 자신의 데이터와 더하고 자신을 다시 리턴해주는 것을 볼 수 있다.

즉, test = test + obj 에서 test에 obj를 더해서 test를 다시 리턴해주는 것이다.

물론 클래스 밖에서 전역함수로 선언하여 구현을 할 수도 있지만(만약 이렇게 한다면 연산자 앞뒤의 객체 두개를 인자로 받아야할 것이다.) 이렇게 한다면, 다른 사람에 의해서 전역함수를 오버로딩하여 클래스의 private멤버들의 값을 수정하는 보안상의 취약점이 생길 수 있기 때문에 클래스의 안에서 구현하는 것이 좋다.


그런데 위의 소스에는 한가지 맹점이 있다.

만약 다음과 같은 코드가 있다고 하자.


위의 코드는 보기에는 아무런 문제가 없어보인다.
하지만 만약 클래스 내에서 동적할당을 하는 부분이 있다고 한다면 심각한 문제를 발생 시킬 수 있다.

클래스의 멤버중 포인터가 동적할당을 받아 가르키고 있다면, 만약 위의 코드로 자신을 대입하게 되면 동적할당을 다시 받아 포인터가 새로 할당받은 메모리를 가르키게 될 것이고, 기존의 할당받은 메모리는 포인터를 잃어버리게 된다.

이것을 계속해서 반복하게 된다면 delete 시켜줄 수 없는 잃어버린 메모리들이 늘어나게 되고 이것은 메모리 누수로 이어지게 되어 시스템에 악영항을 끼치게 된다.

따라서 아래와 같이 고쳐주어야한다.

개인적으로 관심이 좀 있는 분야이기도 해서 공부를 해볼까해서 나름 공부하는 내용들을 정리하는 식으로 포스팅 해볼까 합니다.

=======================================================================================================


우리는 알게 모르게 데이터 압축을 아주 많이 사용하고 있습니다.
알집이나 win zip, win rar 같은 압축 프로그램을 이용해서 파일의 용량을 줄이는 것부터, 정말 많이 쓰이고 있는 mp3나 jpeg같은 것도 데이터 압축이지요.

압축 기술은 오래전 하드웨어의 한계상 많은 용량을 다룰 수 없었을 때 효율적으로 데이터를 보관, 이동등을 하기 위해 사용되어 왔으며, 하드웨어가 비약적으로 발달된 현재에도 그 유용성은 여전히 뛰어납니다.


데이터 압축을 위키 백과사전에서 검색해보면 다음과 같이 나옵니다.


네, 뭐 따로 정의하지 않더라도 이미 다 알고 있는 이야기 같습니다 =ㅅ=;;


데이터 압축은 크게 두 종류로 나눌 수 있습니다. 바로 무손실 압축과 손실 압축인데요.

예를 들자면 알집으로 파일을 압축하면 나중에 압축을 풀었을 때 원본의 데이터가 손상되지 않습니다. 이런 압축 방식을 무손실 압축이라고 합니다. 대표적인 무손실 압축 알고리즘에는 반복 길이 부호화와 허프만 부호화 등이 있습니다.

손실 압축은 압축 이후에는 원래의 데이터의 일부분을 손실했기 때문에 다시 복원할 수 없는 방식인데, 사람이 들을 수 없는 영역을 삭제하여 압축하는 방식인 mp3가 대표적이라 할 수 있습니다.


무손실 압축과 손실 압축을 예를 들어 더 자세하게 알아보도록 하죠.



무손실 압축

압축 알고리즘에 가장 간단한 반복 길이 부호화에 대해 알아보겠습니다.

하얀색 모니터에 검은색 점이 찍혀있는 데이터에 대해 생각해봅시다. 하얀색 픽셀을 w라고 쓰고 검은색 점을 b라고 표현한다면 다음과 같을 것입니다.


위의 데이터를 봤을 때 자세히 보면 반복되는 데이터를 알 수 있습니다. 바로 w가 반복되다가 b가 반복되고 w가 다시 반복되는 식으로 데이터가 이루어져있습니다.

따라서 다음과 같이 표현할 수도 있을 것 같습니다.


w가 5개있고 b가 1개 있고 그뒤로 w가 5개가 있고....이런 식으로 표현을 하게 되면 원래 기존의 데이터는 20개의 글자가 필요했지만 아래의 데이터에서는 14개 글자만 있으면 원래의 데이터를 다시 만들어 낼 수 있습니다.

여기에서 w와 b는 0과 1로 이루어진 비트 데이터일 때도 똑같이 적용될 수 있겠지요.

물론 데이터가 저런식으로 반복되는 경우는 그렇게 많지 않을테고 이를 위한 확장된 여러가지 알고리즘들이 있지만, 기본적으로는 위의 방식과 비슷합니다.

반복 길이 부호화를 사용하는 대표적인 파일 형식으로 PCX, BMP, ILBM 등이 있습니다.



손실 압축

위의 데이터를 다시 살펴봅시다.

위의 데이터는 모니터에 표시된 픽셀이라고 가정했는데, 자세히 보면 b가 하나 인 곳이 있습니다. 만약 모니터가 아주 크고 위의 데이터는 그 중 일부의 데이터라고 한다면, 하나의 픽셀이 검은 것은 없어지더라도 별로 표시가 나지 않을 수 있습니다. 마찬가지로 가장 마지막에 있는 w도 옆의 b로 바꾼다고 해도 그다지 표시가 나지 않을 수 있겠지요.

그렇다면 다음과 같이 바꿀 수도 있을 것 같습니다.


이것을 다시 반복 길이 부호화로 줄인다고 하면, 다음과 같을 것입니다.


무손실 압축에서는 압축이후에 14개의 글자가 필요했지만 이 경우에는 9개만 있으면 됩니다. 물론 이를 원래 데이터로 복원할 방법은 없겠지만, 대신 데이터가 훨씬 더 줄어드는 장점이 있습니다.

손실압축은 멀티미디어에서 아주 많이 쓰이고 있으며, 대표적으로는 JPEG과 mp3, mp4등으로 잘 알려진 MPEG 계통의 압축기술이 있습니다.




참고 사항

위키 백과사전에서 데이터 압축으로 검색을 해보면 여러 압축 기술들의 압축율에 대한 순위가 나와있는데, 잘 알려진 압축 기술들도 있고(zip이라던지 rar, arj 같은), 생소한 기술들도 있습니다.

압축은 텍스트 파일이나 html같은 파일에는 아주 높은 압축율을 보이지만, 이미 압축되어 있는 파일인 mp3나 jpg같은 파일은 그다지 크기가 줄어들지 않으며, 헤더의 추가로 오히려 늘어나는 경우도 있습니다.

순위들을 보면 rk, rar, 7-zip 이 대체적으로 높은 순위에 랭크되어 있습니다. rk와 rar는 사용 프로그램이고, 7-zip은 오픈소스로 윈도우는 물로 리눅스에서도 동작합니다.


개인적으로는 7-zip을 써보고 정말 높은 압축율에 놀랐는데, 압축하는데 무지하게 오래 걸린다는 단점이 좀 있었습니다.

C에서의 동적할당은 malloc같은 함수를 통해 하였다. 그렇다면 C++에서도 객체 포인터를 만든다음에 malloc을 통해 동적할당이 가능할까?

다음의 소스를 보자.


컴파일도 이상없이 되고 test()함수도 호출된다.
하지만 자세히 보면 어떤 문제가 있는데, 그것은 생성자와 소멸자가 호출되지 않는다는 것이다. 이것은 프로그래머가 의도한 동작을 수행하지 못할 가능성이 생길 수 있다.

따라서 C++에서는 다음과 같은 동적할당 키워드를 제공한다.


new 라는 키워드를 통해 동적할당을 하고, delete 키워드를 통해 free시킨다.

다음과 같은 코드도 가능하다.


따라서 C++에서는 malloc 보다는 new를 통해 동적할당을 하는 것이 바람직하다.

또한 다음과 같은 방법도 가능하다.


다만 delete를 할때는 배열이란 것을 명시해줘야 한다. 하지 않는다면 하나만 지우게 된다.

임시 객체는 바로 생성되었다가 사라지는 객체를 말하는데, 몇가지 용도로 쓰인다.

다음 소스를 보자.


#include <iostream.h> class points { public: int x; int y; points(int x, int y) { this->x = x; this->y = y; } }; void Draw(points P) { //점을 찍는다. }; int main() { points P(2, 3); Draw(P); //.... //.... return 0; }

위의 Draw 함수는 점을 찍는 함수라고 가정하자.
인자로는 points의 객체를 받고 있다.
위의 경우에서 Draw 함수에서 점을 찍을 좌표만을 받기위해 객체를 생성해서 인자로 주는데 단지 좌표만을 위해서만 생성한 객체가 메인 함수가 끝날때까지 남아있게된다.

이럴때는 임시객체를 생성하는게 더 효율적일 수 있다.

함수를 호출할 때 다음과 같이 사용하면 된다.
Draw(points(2, 3));