zzun.net

공학수학2 / 2002년 2학기 / 박근수 교수님

[설명]
Huffman Coding : 각 문자의 Frequency를 이용한 텍스트 압축
Huffenc.java : 입력텍스트(Huffman.in)로부터 압축파일(Huffman.cmp)과 빈도파일(Huffman.frq) 생성
Huffdec.java : 압축파일과 빈도파일로부터 출력텍스트(Huffman.out) 생성
HuffmanTree.java : 코딩&디코딩에 사용되는 트리

[Huffenc.java]
import java.io.*;

class HuffOutputStream                                // 비트단위 출력을 담당하는 클래스
{
       public HuffOutputStream(OutputStream os) throws IOException
       {
               buffer = 0;                                        // 한 바이트를 읽어 저장하는 버퍼
               position = 0;                                // 현재 비트가 바이트 내에서 몇번째 비트인지를 가리킴.
               out = new DataOutputStream(os);
       }

       public void writeCode(String code) throws IOException                // 0과 1의 스트링으로 된 코드를 출력
       {
               for (int i=0; i<code.length(); i++)
                       writeBit(code.charAt(i));                                                        // 한 비트씩 출력
       }

       private void writeBit(char c) throws IOException                        // 0 또는 1의 한 비트 출력
       {
               if (c == '1')
                       buffer |= (1<<position);                                                        // '00000001' 을 포지션만큼 왼쪽으로 쉬프트 시켜서 버퍼에 OR 시킴.
               else if (c != '0')
                       throw new IOException("Wrong Code!");
               position++;                                                                                                // 포지션을 한 칸 이동.
               if (position == 8)                                                                                // 마지막 비트까지 채웠으면 파일에 씀
                       flush();
       }

       public void flush() throws IOException                                                // 한 바이트가 되었을때 파일에 씀.
       {
               if (position == 0)                                                                                // 만약 한비트도 써지지 않았으면 아무것도 쓰지 않음
           return;
       out.write(buffer);
       position = 0;                                                                                        // 포지션 초기화
       buffer = 0;                                                                                                // 버퍼 초기화
       }

       public void close() throws IOException
       {
               flush();                                                                                                // 현재까지 쓰여진 1바이트가 안된 비트들을 파일에 씀
               out.close();
       }

       private DataOutputStream out;
       private int buffer;
       private int position;
}

public class Huffenc
{
       public static String inputFileName = "Huffman.in";
       public static String freqFileName = "Huffman.frq";
       public static String outputFileName = "Huffman.cmp";

       public static void main(String[] args) throws IOException
       {
               HuffmanTree tree = new HuffmanTree();

               InputStream fin = new BufferedInputStream(new FileInputStream(inputFileName));
               tree.charCount(fin);                                                                                        // 문자들의 프리퀀시를 셈
               fin.close();

               DataOutputStream freqOut = new DataOutputStream(new FileOutputStream(freqFileName));
               tree.writeFreq(freqOut);                                                                                // 프리퀀시 파일을 씀
               freqOut.close();
               
               fin = new BufferedInputStream(new FileInputStream(inputFileName));                // 한번 더 읽기 위해 다시 open
               HuffOutputStream fout = new HuffOutputStream(new FileOutputStream(outputFileName));
               int buf = fin.read();                                                                                        // 한 글자 읽음
               while (buf != -1)                                                                                                // 파일이 끝날때까지
               {
                       fout.writeCode(tree.getCode(buf));                                                        // 글자를 코드로 변환해서 출력
                       buf = fin.read();                                                                                        // 다시 한 글자 읽음
               }
               fout.writeCode(tree.getCode(tree.EOF));                                                        // 마지막임을 뜻하는 문자 쓰기
               fout.close();
       }
}

[Huffdec.java]
import java.io.*;

class HuffInputStream                                        // 비트단위 입력을 담당하는 클래스
{
       public HuffInputStream(InputStream is) throws IOException
       {
               position = 8;                                        // 현재 비트의 위치 기본값 지정
               in = new DataInputStream(is);   // 바이너리 인풋
       }

       public int readCode(HuffmanTree tree) throws IOException
       {
       String code = "";                                // 코드를 저정할 스트링
       int bit = readBit();                        // 한 비트를 읽어서 저장 (0 또는 1)
               int decodedKey;

       while(true)
       {
           code += bit;                                                                        // 스트링에 방금 읽은 비트 추가
                       decodedKey = tree.getKey(code);                                        // 지금 까지 스트링을 decode 해본다
                       if (bit==-1 || decodedKey==tree.ERROR)                        // EOF가 나오기 전에 파일이 끝나거나 디코딩 에러가 날 경우
                       {
                               System.out.println("Decoding Error!");
                               System.exit(0);
                       }
                       else if (decodedKey == tree.NOT_A_VALUE)                // 아직 하나의 코드가 아닐 경우
                       {
                               bit = readBit();                                                        // 새로운 비트를 읽고 다음 loop을 실행
                               continue;
                       }
                       else
                               return decodedKey;                                                                // 제대로 디코딩 되었으면 디코드한 결과를 리턴
               }
       }

       private int readBit() throws IOException                                // 한 비트를 읽음
       {
               if ( position == 8 )                                                                // 현재 남은 비트가 없으면 (혹은 처음이면)
       {
           buffer = in.read();                                                                // 한 바이트를 읽어서
           if( buffer == -1 )                                                                // 끝이면 끝이라고 리턴
               return -1;
           position = 0;                                                                        // 포지션을 맨 앞으로
       }

               return (buffer & (1<<position++)) == 0 ? 0 : 1;                // '00000001'을 포지션만큼 왼쪽으로 쉬프트시켜서 버퍼랑 AND 시킨 결과가 현재 비트!
       }

       public void close() throws IOException
       {
               in.close();
       }

       private DataInputStream in;
       private int buffer;
       private int position;
}

public class Huffdec
{
       public static String inputFileName = Huffenc.outputFileName;
       public static String freqFileName = Huffenc.freqFileName;
       public static String outputFileName = "Huffman.out";

       public static void main(String[] args) throws IOException
       {
               HuffmanTree tree = new HuffmanTree();
               DataInputStream freqIn = new DataInputStream(new FileInputStream(freqFileName));
               tree.readFreq(freqIn);                                                                                                                                // 프리퀀시 파일을 읽음
               freqIn.close();

               HuffInputStream fin = new HuffInputStream(new FileInputStream(inputFileName));
               OutputStream fout = new BufferedOutputStream(new FileOutputStream(outputFileName));
               int currentChar = fin.readCode(tree);                                                                                        // 디코드된 글자 하나를 읽음
               while (currentChar != tree.EOF)                                                                        // 마지막 이전까지
               {
                       fout.write(currentChar);                                                                                        // 글자를 씀
                       currentChar = fin.readCode(tree);                                                                        // 다시 글자 하나를 읽음
               }
               fin.close();
               fout.close();
       }
}

'IT > 소스코드' 카테고리의 다른 글

[Java] Polynomial Calculator 2/2  (0) 2003.07.10
[Java] Polynomial Calculator 1/2  (0) 2003.07.10
[Java] Huffman Coding 2/2  (0) 2003.07.10
[Java] Huffman Coding 1/2  (0) 2003.07.10
[C++] Vigenere Cipher and Cryptanalysis  (0) 2003.07.10
[C++] class String  (0) 2003.06.09

Comment +0

공학수학2 / 2002년2학기 / 박근수 교수님

[설명]
Vigenere Cipher and Cryptanalysis : n만큼의 길이를 가지는 Key를 이용해 암호화. 그리고 그 Key 없이 암호분석.
vigen.cpp : Key를 이용하여 Plaintext(vigen.in)를 Ciphertext(vigen.out)으로 바꿈.
vigcr.cpp : Ciphertext로부터 Key를 유추하여 Plaintext(vigcr.out)을 만들어냄.
vigen.in : 첫줄에는 Key가 있어야 함. Key는 반드시 대문자. 나머지 plaintext는 소문자.
vigen.out : <vigen> 실행시 자동 생성됨. Ciphertext.
vigcr.out : <vigcr> 실행시 자동 생성됨. 정상적으로 동작할 경우 vigen.in과 같은 파일임.

[vigen.cpp]
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>

void main()
{
       char buffer[42]; // 읽어들인 스트링을 임시로 저장할 버퍼
       char cipher[41] = {0}; // 변환된 스트링을 저장할 배열
       char key[20]; // 키를 저장할 배열
       
       char inputFile[] = "vigen.in";
       char outputFile[] = "vigen.out";

       ifstream input(inputFile);
       ofstream output(outputFile); // 입출력 스트림

       if (!input) {cerr << "Error in file name" << endl; return;} // 파일이 없을때
       else
       {
               input.getline(buffer, 30); // 첫라인(키)를 읽어들임

               int keylen = strlen(buffer);
               if (keylen<5 || keylen>20) {cerr << "Error in Key length." << endl; return;} // 키 길이가 맞는지 검사
               else
               {
                       for(int i=0; i<keylen; i++) // 키가 전부 알파벳 대문자가 맞는지 검사
                               if (buffer[i]<65 || buffer[i]>91) {cerr << "Error in Key String." << endl; return;}
                       strcpy(key, buffer); // 다 획안되면 버퍼의 내용을 키에 복사
               }

               printf("Key : %s\n",key); // 키를 출력
               printf("%-40s%-40s","Input : Plaintext","Output : Cyphertext");

               while (!input.eof())
               {
                       input.getline(buffer, 42); // 한 줄씩 입력 받음

                       int j=0;

                       /* 혹시 마지막줄이 40글자가 안될때를 대비해서 새로운 줄을 읽을때마다 초기화 */
                       for (int i=0; i<(int)strlen(cipher); i++) cipher[i] = ' ';

                       printf("%-40s",buffer);

                       for (i=0; i<(int)strlen(buffer); i++)
                       {
                               cipher[i] = (buffer[i] - 'a' + key[j++] - 'A') % 26 + 'A';
                               if (j>=(int)strlen(key)) j=0;
                       }

                       printf("%-40s",cipher); // 콘솔에 출력

                       output << cipher << endl; // 파일에 출력
               }
       }
       
       char garbage;
       cout << "\n\nPress Ctrl+C To End The Program.";
       cin >> garbage; // 출력 결과를 볼 수 있도록 기다림.

       return;
}

[vigcr.cpp]
#include <fstream.h>
#include <string.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>

char inputFile[] = "vigen.out";
char outputFile[] = "vigcr.out";
char* cipher; // 입력받는 cipher text를 저장할 array.

int size_of_input_file(void); // input file의 크기를 계산하는 함수. (동적할당을 위해)
void read_ciphertext(void); // input을 읽는 함수.
int determine_m(int*); // 키의 길이를 결정하는 함수.
void compute_ic(int, double*); // m이 주어질 때 각 줄의 index of coincidence를 계산하는 함수.
int rel_shift(int, char*); // m값으로 배열해서, 각 Mutual IC를 이용한 Relative Shift를 수행하는 함수.
void compute_prob(double**, int); // m줄로 배열했을때, 각 줄의 알파벳 확률(MIC를 구하기 위해)을 계산하는 함수.
int compute_gap(int, int, int, double**); // 두 줄의 Mutual IC를 이용해 gap을 판단하는 함수.
char find_uni_key(void); // Relative Shift를 마친 후 하나의 키를 찾는 과정.

void main()
{        
       int m;

       cipher = (char*)calloc(size_of_input_file(), sizeof(char));
       /* 인풋파일의 크기를 미리 읽어서 cipher text를 저장할 array를 동적할당. */

       read_ciphertext();

       int m_except[16]; // 잘못 계산된 m (다음 계산때 제외할 m)
       
       m = determine_m(m_except);

       char* key = (char*)calloc(m+1, sizeof(char));
       /* 키를 저장할 char array 선언, 할당 */

       int m_ok = rel_shift(m, key); // m이 정확한지를 판단하는 값 m_ok
       /* m을 이용해 relaive shift를 한다. key[]에는 첫번째 키와의 gap을 넣는다. */

       while (!m_ok) // rel_shift가 올바른 값(1)을 리턴할때 까지
       {
               static int a = 0;
               m_except[a++] = m; // 잘못계산된 m 값을 배열에 저장
               m = determine_m(m_except); // 이전에 계산한 m값들을 제외하고 m 계산
               m_ok = rel_shift(m, key);
       }

       key[0] = find_uni_key(); // 키의 첫번째 글자를 찾는다.

       for (int i=1; i<m; i++)
               key[i] = (key[i] + key[0] - 'A') % 26 + 'A'; // 찾아낸 첫번째 글짜를 이용해 나머지 글자를 채운다.

       key[i] = '\0'; // 스트링으로 쓰기 위해 마지막에 널문자를 넣어준다.
       
       ofstream out(outputFile);

       cout << "Found Key : " << key; // 콘솔로 키를 출력.
       out << key; // 파일로 키를 출력.

       for (i=0; i<(int)strlen(cipher); i++) // 찾은 키를 이용해 사이퍼텍스트를 shift 시킨다.
               cipher[i] = (cipher[i] - key[0] + 26) % 26 + 'a'; // gap 만큼은 이미 shift 되어 있으므로 키 첫글자 만큼만!

       for (i=0; i<(int)strlen(cipher); i++)
       {
               if (i%40 == 0) // 한줄에 40글자씩 출력하기 위해 다음줄로...
               {
                       cout << endl;
                       out << endl;
               }
               cout << cipher[i]; // 콘솔에 출력.
               out << cipher[i]; // 파일로 출력.
       }
       out << endl;

       free(key);

       free(cipher);

       char garbage;
       cout << "\n\nPress Ctrl+C To End The Program.";
       cin >> garbage; // 출력 결과를 볼 수 있도록 기다림.

       return;
}

int size_of_input_file(void) // 인풋파일의 사이즈 계산
{
       char buf[42];
       int c = 0;

       ifstream in(inputFile);
       while(!in.eof())
       {
               in.getline(buf, 42);
               c++; // 라인 수를 카운트
       }

       in.close();

       return c*40; // 계산한 값을 리턴
}

void read_ciphertext()
{
       char buf[42];

       ifstream in(inputFile);
       while(!in.eof())
       {
               in.getline(buf, 42);
               strcat(cipher, buf); // 한줄씩 읽어서 cipher에 계속 덧붙임.
       }

       for (int i=0; i<(int)strlen(cipher); i++)
               if (cipher[i]<'A' || cipher[i]>'Z')
               {
                       cipher[i] = '\0';
                       break;
               } // 입력받은 array에 알파벳을 제외한 다른 문자가 있을 경우 그곳에서 짤라서 프로그램이 정상적으로 돌아가게 함.
       
       in.close();

       return;
}

int determine_m(int* ex)
{
       int candi_m, det_m = 0; // m이 될수있는 후보, 선택된 m
       double ic_avg, ic_avg_max = 0; // index of coincidence의 평균, 그 평균의 최대값.
       double diff, diff_min = 1; // IC와 0.065와의 차이. 그 차이의 최소값.
       for (int m=5; m<=20; m++)
       {
               int i;
               double *ic = (double*)calloc(m, sizeof(double)); // IC 값들을 저장할 배열
               for(int k=0; k<16; k++)
                       if (ex[k] == m) goto END_OF_LOOP;
               compute_ic(m, ic);
               ic_avg = 0;
               diff = 0;
               for (i=0; i<m; i++)
               {
                       diff += fabs(0.065-ic[i]); // 각 줄의 IC들이 0.065에서 얼마나 떨어져 있나를 알아봄.
                       ic_avg += ic[i];
               }
               free(ic);
               diff = diff/m; // m개의 IC가 있으므로 균형을 맞추기 위해 m으로 나눔.
               ic_avg = ic_avg/m;

               if ((0.065-ic_avg) < (ic_avg-0.038)) // IC의 평균의 0.038보다 0.065에 더 가까울 때.
               {
                       if (diff_min > diff) // diff가 최소인 값을 m으로 택한다.
                       {
                               diff_min = diff;
                               det_m = m;
                       }
               }
               else // 만약 0.038보다 0.065에 더 가까운 값이 없을 때.
                       if (ic_avg_max < ic_avg) // 평균이 가장 큰 값을 m으로 택하기 위해 후보로 둔다.
                       {
                               ic_avg_max = ic_avg;
                               candi_m = m;
                       }
               END_OF_LOOP :;
       }

       if (det_m == 0) // det_m이 결정되지 않았을 때.
               return candi_m;
       else
               return det_m;
}

void compute_ic(int m, double* ic) // IC를 계산하는 루틴.
{
       for (int i=0; i<m; i++)
       {
               int n = 0;
               int count[26] = {0};
               while (cipher[n*m + i] >= 'A' && cipher[n*m + i] <= 'Z') // i번째 글자, (m+i)번째 글자, (2m+i)번째 글자.. 순으로 읽는다.
               {                        
                       count[cipher[n*m + i]-'A']++; // 그 글자에 해당하는 카운트를 1 더한다.
                       n++;
               }
               for (int j=0; j<26; j++)
                       ic[i] += (double)(count[j]*(count[j]-1))/(n*(n-1)); // 카운트한 값으로 IC를 구한다.
       }
}

int rel_shift(int m, char* key)
{
       double **p; // MIC를 계산하기 위해 각 줄마다 알파벳이 등장할 확률을 저장할 2차원 array
       p = (double**)calloc(m, sizeof(double*)); // m개의 줄 할당
       for (int i=0; i<m; i++)
               p[i] = (double*)calloc(26, sizeof(double)); // 각 줄마다 26개의 칸 할당
       
       compute_prob(p, m); // 각 줄의 알파벳 확률 계산

       int* gap = (int*)calloc(m, sizeof(int)); // key의 첫글자와 나머지 글자들 간의 gap을 저장할 array

       for (i=1; i<m; i++)
               gap[i] = compute_gap(m, 0, i, p); // 첫번째 줄 과 나머지 줄간의 gap 계산.

       for (int j=2; j<m; j++) // gap이 정확한지 확인하는 루틴
       {
               int temp_gap = (compute_gap(m,1,j,p) + gap[1]) % 26; // key의 두번째 글자와의 gap을 계산해서 gap[1]과 더함.
               if (temp_gap != gap[j]) // 만약 첫번째 계산결과와 두번째 계산결과가 다르다고 나오면...
               {
                       int temp_gap_2 = (compute_gap(m,2,j,p) + gap[2]) % 26; // key의 세번째 글자와의 gap을 계산해서
                       if (temp_gap_2 == gap[j]) // 세개의 gap 중에 같은 두개의 gap을 선택!!
                               break;
                       else if (temp_gap_2 == temp_gap)
                               gap[j] = temp_gap;
                       else // 만약 세개의 gap이 모두 다르다고 나오면
                       {
                               int temp_gap_3 = (compute_gap(m,3,j,p) + gap[3]) % 26; // 한번더 계산
                               if (temp_gap_3 == gap[j])
                                       break;
                               else if (temp_gap_3 == temp_gap)
                                       gap[j] = temp_gap;
                               else if (temp_gap_3 == temp_gap_2)
                                       gap[j] = temp_gap_2; // 넷 중에 같은 두개의 gap이 맞는 것이라고 판단!!
                               else
                               {
                                       // 넷 모두 다르다면 키가 정확하지 않을 가능성이 많음!!
                                       // 이 경우엔 m이 잘못 계산됐거나, 통계적으로 잘 맞지 않는 plaintext일 가능성이 높음.
                                       free(gap);
                                       for (i=0; i<m; i++)
                                               free(p[i]);
                                       free(p); // 동적할당 변수들을 모두 free
                                       return 0; // 잘못된 결과임을 return
                               }
                       }
               }
       }
       
       for (i=1; i<m; i++)
       {
               int n = 0;
               while (cipher[n*m+i] >= 'A' && cipher[n*m+i] <= 'Z')
               {
                               cipher[n*m+i] = (cipher[n*m+i] - 'A' - gap[i] + 26) % 26 + 'A';
                               n++;  // 계산한 gap을 이용해서 ciphertext의 각 줄을 gap 만큼 shift
                                         // 그렇게 되면 cipher 텍스트 전체가 한글자의 key로 shift시킨것과 같게 된다!
               }
               key[i] = gap[i]; // gap값을 key에 저장.
       }

       free(gap);
       
       for (i=0; i<m; i++)
               free(p[i]);
       free(p);

       return 1; // 정상적으로 return
}

void compute_prob(double** p, int m) // 각 줄의 알파벳 확률 계산
{
       for (int i=0; i<m; i++)
       {
               int n = 0;
               while (cipher[n*m+i] >= 'A' && cipher[n*m+i] <= 'Z')
               {
                       p[i][cipher[n*m+i]-'A']++;
                       n++;
               }
               for (int j=0; j<26; j++)
                       p[i][j] = p[i][j] / n;
       }
}

int compute_gap(int m, int i, int j, double** p) // MIC를 이용해 i와 j열 간의 gap 판단하기
{
       int gap;
       double mic[26] = {0};
       double curr_diff, diff_min = 1; // 현재 MIC의 0.065와의 차, 그 차의 최소값.
       for (int l=0; l<26; l++) // l을 0부터 25까지 돌리면서 적절한 gap을 찾는다.
       {
               for (int k=0; k<26; k++)
                       mic[l] += p[i][k] * p[j][(k+l)%26];
               curr_diff = fabs(0.065 - mic[l]);
               if (curr_diff < diff_min) // diff가 최소인 gap 찾는다.
               {
                       diff_min = curr_diff;
                       gap = l;
               }
               if (curr_diff < 0.005) break; // 단 diff가 일정기준 이상으로 아주 작으면 그 값을 택한다.
       }
       return gap;
}

char find_uni_key() // cipher가 한글자의 key로 shift된 상태일때, 그 한글자의 key를 찾는다.
{
       int count[26] = {0};
       for (int i=0; i<(int)strlen(cipher); i++)
               count[cipher[i]-'A']++;
       int count_max = count[0];
       char uni_key = ('A' - 'E' + 26) % 26 + 'A'; // 일단 key가 A라고 생각.
       for (i=1; i<26; i++)
       {
               if (count_max < count[i])
               {
                       count_max = count[i];
                       uni_key = ('A' + i - 'E' + 26) % 26 + 'A'; // count가 최대인 값이 plaintext에서 e에 해당한다고 보고 uni_key 계산
               }
       }

       return uni_key;
}

'IT > 소스코드' 카테고리의 다른 글

[Java] Polynomial Calculator 2/2  (0) 2003.07.10
[Java] Polynomial Calculator 1/2  (0) 2003.07.10
[Java] Huffman Coding 2/2  (0) 2003.07.10
[Java] Huffman Coding 1/2  (0) 2003.07.10
[C++] Vigenere Cipher and Cryptanalysis  (0) 2003.07.10
[C++] class String  (0) 2003.06.09

Comment +0

#include <string.h>

class String {
private:
       char* _string;
       int _length;

public:
       String() : _string(NULL), _length(0) {}

       String(const String& s) : _string(NULL), _length(0) {
               _length = s._length;
               if (_length > 0) {
                       _string = new char [s._length + 1];
                       strcpy (_string, s._string);
               }
       }

       String(const char* s) : _string(NULL), _length(0) {
               if (s != NULL) {
                       _length = strlen(s);
                       _string = new char [_length + 1];
                       strcpy (_string, s);
               }
       }

       String(const char* s, int size) : _string(NULL), _length(0) {
               if (s != NULL) {
                       _length = size;
                       _string = new char [_length + 1];
                       memcpy (_string, s, size);
                       _string[_length] = '\0';
               }
       }

       String operator = (const String& s) {
               if (this != &s) {
                       if (_string)
                               delete [] _string;
                       _length = s._length;
                       _string = new char [_length + 1];
                       strcpy (_string, s._string);
               }
               return *this;
       }

       ~String() { delete [] _string; }
};

'IT > 소스코드' 카테고리의 다른 글

[Java] Polynomial Calculator 2/2  (0) 2003.07.10
[Java] Polynomial Calculator 1/2  (0) 2003.07.10
[Java] Huffman Coding 2/2  (0) 2003.07.10
[Java] Huffman Coding 1/2  (0) 2003.07.10
[C++] Vigenere Cipher and Cryptanalysis  (0) 2003.07.10
[C++] class String  (0) 2003.06.09

Comment +0


티스토리 툴바