kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

ソースコードをハフマン符号で暗号化する【C言語】

C言語のソースコードをハフマン符号化するPythonスクリプトです．暗号化後のソースコードは人にはまともに読めませんがコンパイルはできます．いわゆる難読化っていうやつです．C言語のdefine文でトークン毎でハフマン符号化します．

動機

汚コードグランプリ！秀逸な汚コードにまみれた解答臭をご覧あれ #逆リファクタリング｜CodeIQ MAGAZINE という「逆リファクタリング」という企画がありました．その中で個人的に一番面白かったものにソースコードをハフマン符号化してみたというのがありました．今回はC言語のソースコードのハフマン符号化をやってみます．

ハフマン符号 - Wikipedia ハフマン符号に関する説明はWikipediaさんに投げる

元のソースコード

変換するC言語のソースコードは以下のソースコードを扱います．

#include<stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    int i;
    for (i = 1; i <= n; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            printf("FizzBuzz\n");
        } else if (i % 3 == 0) {
            printf("Fizz\n");
        } else if (i % 5 == 0) {
            printf("Buzz\n");
        } else {
            printf("%d\n", i);
        }
    }
    return 0;
}

入力を受け取り，FIzzBuzzを行なうプログラムです．このソースコードをハフマン符号化します．

ハフマン符号化スクリプト

Pythonで作成したハフマン符号化スクリプトが以下になります．

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os;
import sys;
import re;

token_frequency = {}
converter = {}
ignore = ['','#include<stdio.h>']

TRUE_STRING = 'I'
FALSE_STRING = 'O'

with open(sys.argv[1], 'r') as input_file:
    for line in input_file:
        tokens = re.split('[ \n\t]+', line)
        tokens.remove('')
        for token in tokens:
            if token in ignore:
                if token : print token
                continue
            if token in token_frequency:
                token_frequency[token] += 1
            else:
                token_frequency[token] = 1
    print
    index = 0
    for source, frequency_num in sorted(token_frequency.items(), key=lambda x:x[1], reverse=True):
        pattern = format(index, 'b')
        target = pattern.replace('1', TRUE_STRING).replace('0', FALSE_STRING); 
        if source in ignore:
            continue
        print "#define", target, source
        converter[source] = target
        index += 1

    input_file.seek(0);

    for line in input_file:
        tokens = re.split('[ \n\t]+', line)
        for token in tokens:
            if token and (not token in ignore):
                print converter[token],
        print

スペース区切りで出て来たトークンを記憶し出現回数を数えます．あとは出現回数の少ない順に短い文字列を割り当てていきます．1に"I"，0に"O"を使い，文字列がビット列ぽく見えるようにしてます．

include文はdefine文より上に書いてないとコンパイルエラーになるので，include文はそのまま表示するようにしました．ソースコードに書かれているinclude文は前もって，ignoreの中に書いておくというダサい実装になってます．

結果

#include<stdio.h>

#define O }
#define I {
#define IO (i
#define II %
#define IOO ==
#define IOI int
#define IIO if
#define III 0)
#define IOOO else
#define IOOI 3
#define IOIO 5
#define IOII i
#define IIOO n;
#define IIOI &&
#define IIIO <=
#define IIII printf("Fizz\n");
#define IOOOO for
#define IOOOI 0;
#define IOOIO scanf("%d",
#define IOOII 0
#define IOIOO =
#define IOIOI i;
#define IOIIO return
#define IOIII i);
#define IIOOO main(void)
#define IIOOI &n);
#define IIOIO 1;
#define IIOII printf("FizzBuzz\n");
#define IIIOO printf("Buzz\n");
#define IIIOI printf("%d\n",
#define IIIIO i++)


IOI IIOOO I
IOI IIOO
IOOIO IIOOI
IOI IOIOI
IOOOO IO IOIOO IIOIO IOII IIIO IIOO IIIIO I
IIO IO II IOOI IOO IOOII IIOI IOII II IOIO IOO III I
IIOII
O IOOO IIO IO II IOOI IOO III I
IIII
O IOOO IIO IO II IOIO IOO III I
IIIOO
O IOOO I
IIIOI IOIII
O
O
IOIIO IOOOI
O

ハフマン符号化成功！！，普通にコンパイルも出来ます．

トークン毎にスペースで区切ったバージョン

#include<stdio.h>

int main () {
    int n ;
    scanf ( "%d" , &n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( i % 3 == 0 && i % 5 == 0 ) {
            printf ( "FizzBuzz\n" ) ;
        } else if ( i % 3 == 0 )  {
            printf ( "Fizz\n" ) ;
        } else if ( i % 5 == 0 ) {
            printf ( "Buzz\n" ) ;
        } else {
            printf ( "%d\n" , i ) ;
        }
    }
    return 0 ;
}

意図的にスペースを入れて，ソースコード中のトークンを分割しています．この方が綺麗にハフマン符号化されます．

#include<stdio.h>

#define O )
#define I (
#define IO ;
#define II i
#define IOO {
#define IOI }
#define IIO 0
#define III printf
#define IOOO %
#define IOOI ==
#define IOIO int
#define IOII if
#define IIOO else
#define IIOI ,
#define IIIO 3
#define IIII 5
#define IOOOO n
#define IOOOI <=
#define IOOIO &n
#define IOOII "%d"
#define IOIOO for
#define IOIOI scanf
#define IOIIO "Fizz\n"
#define IOIII 1
#define IIOOO "FizzBuzz\n"
#define IIOOI main
#define IIOIO =
#define IIOII return
#define IIIOO ()
#define IIIOI &&
#define IIIIO "%d\n"
#define IIIII ++
#define IOOOOO "Buzz\n"


IOIO IIOOI IIIOO IOO
IOIO IOOOO IO
IOIOI I IOOII IIOI IOOIO O IO
IOIOO I IOIO II IIOIO IOIII IO II IOOOI IOOOO IO IIIII II O IOO
IOII I II IOOO IIIO IOOI IIO IIIOI II IOOO IIII IOOI IIO O IOO
III I IIOOO O IO
IOI IIOO IOII I II IOOO IIIO IOOI IIO O IOO
III I IOIIO O IO
IOI IIOO IOII I II IOOO IIII IOOI IIO O IOO
III I IOOOOO O IO
IOI IIOO IOO
III I IIIIO IIOI II O IO
IOI
IOI
IIOII IIO IO
IOI

綺麗にトークン毎にハフマン符号化されました．