Monthly Archives: 4月 2013

Bashでインタプリタ(Brainf*ck)を書いてみる

ワケありましてBrainf*ckを書くことになりBashでこんなものを書く人は少ないかもなと思いながら実装してみました。
とりあえずWikipediaで公開されている”Hello, world!”は実行出来ます。
色んなところで公開されている”FizzBuzz”も試した限りでは動作しているようです。

#!/bin/bash
############################################################################
#
# メモ
#
# このソースコードは私のサーバにて一般公開しております
# 公開先: https://www.orsx.net/archives/4469
#
# Bashは明確にローカル変数であることを宣言しなければ
# 全てグローバル変数となるが・・・・
# とりあえず初期化する関数を定義すれば追いやすくなるかもしれないとかと
# べ、別にこんなもの無くても問題ない。。。
#
# 言語によっては最後に標準出力した値を返り値として返す物があったりするため
# 癖で関数の最後には必ず明的にreturnしてあるが・・・
# べ、別にこんなもの無くても問題ない。。。
#
# ちなみに、変数は下記のようになっている
# ・グローバル変数は大文字
# ・ローカル変数は小文字
#
############################################################################

# 使用するグローバル変数を明的に初期化する
function initialize() {
  # 変数
  TEXT_SRC=""
  CODE_LEN=0
  CODE_PTR=0
  BUFF_PTR=0
  BUFF_LEN=0

  # 配列
  CODE=()
  BUFF=()

  return
}

# EOF(CTRL+D)が来るまで読み続け改行は無視する
# グローバル変数SRCにソースコードを格納する
function readstring() {
  local line
  while read line
  do
    # 文字列連結 連結演算子は存在しない
    TEXT_SRC=$TEXT_SRC$line
  done

  # returnは数字しか返せない
  return
}

# 標準入力で1文字だけ受け取る
function readchar() {
  local line
  read line
  # 文字を数字に変換
  BUFF[${BUFF_PTR}]=$(printf "%d" "'${line:0:1}")

  return
}

# ASCIIコードからアルファベットを表示する
function echochar() {
  echo ${BUFF[${BUFF_PTR}]} | awk '{ printf("%c", $0); }'

  return
}

# 初期化されていない配列の要素を使おうとする前に初期化して拡張する
# これによりバッファーの長さを制限しなくて良くなる
function expansion() {
  if [ ${BUFF_PTR} -gt ${BUFF_LEN} ]
  then
    BUFF_LEN=$((BUFF_LEN+1))
    BUFF[${BUFF_LEN}]=0
  fi

  return
}

# ソースコードをグローバル配列CODEに一文字ずつ格納する
function tokenizer() {
  # トークンを格納する配列の添字を数える
  CODE_LEN=$((${#TEXT_SRC}-1))

  # 文字列から一文字ずつトークンを取り出し配列に追加していく
  local i
  for i in $(seq 0 ${CODE_LEN})
  do
    CODE[${i}]=${TEXT_SRC:${i}:1}
  done

  return
}

# BUFF_PTRがな0ら対応する']'まで直後までジャンプする
function left_jumper() {
  if [ ${BUFF[${BUFF_PTR}]} -eq 0 ]
  then
    local loop_ptr=1
    while [ ${loop_ptr} -ne 0 ]
    do
      CODE_PTR=$((CODE_PTR+1))
      case ${CODE[${CODE_PTR}]} in
      '[')
        loop_ptr=$((loop_ptr+1));;
      ']')
        loop_ptr=$((loop_ptr-1));;
      esac
    done
  fi

  return
}

# BUFF_PTRがな0ら対応する'['の直後までジャンプする
function rite_jumper() {
  if [ ${BUFF[${BUFF_PTR}]} -ne 0 ]
  then
    local loop_ptr=1
    while [ ${loop_ptr} -ne 0 ]
    do
      CODE_PTR=$((CODE_PTR-1))
      case ${CODE[${CODE_PTR}]} in
      ']')
        loop_ptr=$((loop_ptr+1));;
      '[')
        loop_ptr=$((loop_ptr-1));;
      esac
    done
  fi

  return
}

# 意味解析を行い実行する
function execute() {
  while [ ${CODE_PTR} -le ${CODE_LEN} ]
  do
    case ${CODE[${CODE_PTR}]} in
    '>')
      BUFF_PTR=$((BUFF_PTR+1));;
    '<')
      BUFF_PTR=$((BUFF_PTR-1));;
    '+')
      BUFF[${BUFF_PTR}]=$((BUFF[${BUFF_PTR}]+1));;
    '-')
      BUFF[${BUFF_PTR}]=$((BUFF[${BUFF_PTR}]-1));;
    '.')
      echochar;;
    ',')
      readchar;;
    '[')
      left_jumper;;
    ']')
      rite_jumper;;
     * )
      local message="Unknown Token! : ";
      echo $message${CODE[${CODE_PTR}]};
      break;;
    esac

    expansion
    CODE_PTR=$((CODE_PTR+1))
  done

  echo "";

  return
}

initialize   # 初期化
readstring   # 入力受付・プリプロセッサ
tokenizer    # 構文解析
execute      # 意味解析・実行

実行方法
直接標準入力で渡すかもしくは
適当なファイル例えば”script.bf”のようなファイルにソースコードを書き込み下記のように実行することができます。
# cat script.bf | brainfuck.sh

2013/05/07 追記
Bashでは”文字”に対して足し算を行えないようなので
文字入力時に整数型に変換するように”,”の処理を修正しました。

Postfixメールボム対策 キューの管理

メールボムの送信側の対策はすでにこちらに紹介しているのですが
キューが溜まり/varの容量がいっぱいになりサーバがダウンする問題について対策方法を見つけたのでメモしておきます。

# 再送を試みる単位の最短時間
minimal_backoff_time = 30s

# 再送を試みる単位の最長時間
maximal_backoff_time = 300s

# 配送できないメッセージがキューに入っている最大の時間
maximal_queue_lifetime = 600s

# 配送できないと見なすまでバウンスメッセージがキューに入っている最大の時間
bounce_queue_lifetime = 600s

# キューを確認する間隔
queue_run_delay = 30s

参考サイト
Postfix設定パラメータ

Perl IPアドレスを10進数の整数型に変換し戻す

データベースにIPアドレスを格納する時は整数型にしたほうがブロックで検索出来たりと後々取り扱いが楽だったりするので変換する変換方法を書いてみる

#!/usr/bin/perl
use utf8;
use strict;
use warnings;

my $addr_i = &addr_s_to_i("192.168.1.1");
my $addr_s = &addr_i_to_s($addr_i);
print "INTEGER:" . $addr_i . "\n";
print "STRING :" . $addr_s . "\n";

# IPアドレスを文字列型から整数型に変換
sub addr_s_to_i {
    my $addr = shift;

    # "."ごとに8bitずつ区切りそれを2進数に変換し配列に入れる
    my @addrs;
    foreach my $addr_split (split('\.', $addr)){
        push(@addrs, sprintf("%08b", $addr_split));
    }

    # 区切った2進数を連結する
    my $bin = join('', @addrs);
    # 2進数を10進数に変換
    my $result = oct('0b' . $bin);

    return $result;
}

# IPアドレスを整数型から文字列型に変換
sub addr_i_to_s {
    my $addr = shift;

    # 10進数を32bitの2進数に変換
    my $bin = sprintf("%032b", $addr);

    # 2進数を8bitごとに区切り10進数に変換し配列に入れる
    my @addrs;
    foreach my $addr_split ($bin =~ m/.{8}/g){
        push(@addrs, oct('0b' . $addr_split));
    }

    # "."ごとに区切り連結する
    my $result = join('.', @addrs);

    return $result;
}

実行結果
INTEGER:3232235777
STRING :192.168.1.1

Perlに変数の型は無いが変数の型を意識しないプログラムは書いてはいけない

Perlには変数の型は無いですが最近変数の容量を見なければならない機会があり調べていたところPerlの変数には型は存在しないが型を意識したプログラムを書かなければならない事が分かったためメモしておく。

#!/sur/bin/perl
use utf8;
use strict;
use warnings;

use Devel::Size qw(size total_size);

my $DATA = 1000;
my $INIT = "";

# 直接操作した場合
{
    print "[variable]\n";

    my $data = $DATA;
    my $init = $INIT;

    my $res = $init;
    for(my $i = 0; $i < $data; $i++){
        $res .= "*";
    }

    print "Before initialization :". size($res) . "\n";

    $res = $INIT;

    print "After initialization  :". size($res) . "\n";
}

# 関数の場合
{
    print "[function]\n";

    my $res = &routine($DATA, $INIT);

    print "Before initialization :". size($res) . "\n";

    $res = &routine(0, $INIT);

    print "After initialization  :". size($res) . "\n";

    sub routine {
        my $data = shift;
        my $init = shift;

        my $result = $init;
        if($data){
            for(my $i = 0; $i < $data; $i++){
                $result .= "*";
            }
        }
        return $result;
    }
}

# メソッドの場合
{
    print "[ method ]\n";

    my $mt = MemTester->new();

    my $res = $mt->routine($DATA, $INIT);

    print "Before initialization :". size($res) . "\n";

    $res = $mt->routine(0, $INIT);

    print "After initialization  :". size($res) . "\n";


    package MemTester;

    sub new {
        my ($class, @args) = @_;
        my %args = ref $args[0] eq 'HASH' ? %{$args[0]} : @args;
        my $self = {%args};

        return bless $self , $class;
    }

    sub routine {
        my $self = shift;
        my $data = shift;
        my $init = shift;

        my $result = $init;
        if($data){
            for(my $i = 0; $i < $data; $i++){
                $result .= "*";
            }
        }
        return $result;
    }
}

最初の値を整数(“$INIT = 0”)で初期化した場合の実行結果
[variable]
Before initialization :1056
After initialization :1056
[function]
Before initialization :1056
After initialization :1056
[ method ]
Before initialization :1056
After initialization :1056

最初の値を文字(“$INIT = ””)で初期化した場合の実行結果
[variable]
Before initialization :1048
After initialization :1048
[function]
Before initialization :1048
After initialization :48
[ method ]
Before initialization :1048
After initialization :48

このように、文字列と数値を混同して使用した変数は多くメモリを消費することが分かる。
さらに、返り値としてデータを受け取った場合、その分受け取った変数もメモリを無駄に使用するためさらに効率は低下する。

Webページを取得するなど文字列を大量に格納し返すようなプログラムを書く場合は取得に失敗した場合は0を返すのではなく””を返すべきである。

数字(例:0)より文字列(例:”0″)の方がメモリを多く使用することは当然のことであるが、変に気取って返り値を混同するような関数やメソッドは書いてはならない事が分かった。

Perl cpanでインストールしたIP::Countryのデータベースを更新する 更新スクリプトの作成 CentOS

IP::Countryには”whois_filenames”と呼ばれるDB更新用のスクリプトが同封されているがインストールされないためcpanでインストール後は非常に困る。その上、更新用スクリプトを単純にコピーして実行しても正しく動作しないため、今回アップデート用のスクリプトを改良しインストール後でも使用出来るようにしておく。

なお、更新用スクリプトはメモリを非常に使うためマシン側では物理的に4GB以上のメモリを搭載している必要があるかもしれない。

“dbmScripts”ディレクトリの存在確認
# ls ~/.cpan/build/IP-Country-2.27/dbmScripts/

“IP::Country”のインストール場所の確認
# ls /usr/lib/perl5/site_perl/5.8.8/IP/

“dbmScripts”ディレクトリのコピー
# cp -R ~/.cpan/build/IP-Country-2.27/dbmScripts/ /usr/lib/perl5/site_perl/5.8.8/IP/

“dbmScripts”ディレクトリへ移動
# cd /usr/lib/perl5/site_perl/5.8.8/IP/dbmScripts/

アップデート用スクリプトをbashにて作成
# vi whois_filenames

#!/bin/bash

wget ftp://ftp.ripe.net/ripe/dbase/split/ripe.db.inetnum.gz && gunzip ripe.db.inetnum.gz
wget ftp://ftp.ripe.net/pub/stats/afrinic/delegated-afrinic-extended-latest
wget ftp://ftp.ripe.net/pub/stats/apnic/delegated-apnic-extended-latest
wget ftp://ftp.ripe.net/pub/stats/arin/delegated-arin-extended-latest
wget ftp://ftp.ripe.net/pub/stats/lacnic/delegated-lacnic-extended-latest

perl ipcc_loader.pl && perl ipcc_maker.pl && perl ipauth_loader.pl && perl ipauth_maker.pl

rm -f *extended-latest* ripe.db.inetnum* sorted_*.txt*

読み込むファイル名が異なるため修正

# vi ipauth_loader.pl

69行目付近

read_reg('delegated-afrinic-extended-latest'); # 修正
read_reg('delegated-lacnic-extended-latest');  # 修正
read_reg('delegated-apnic-extended-latest');   # 修正
read_ripe();
read_reg('delegated-arin-extended-latest');    # 修正

join_neighbours();
punch_holes();
optimize();
output();

# vi ipcc_loader.pl

69行目付近

read_reg('delegated-afrinic-extended-latest'); # 修正
read_reg('delegated-lacnic-extended-latest');  # 修正
read_reg('delegated-apnic-extended-latest');   # 修正
read_ripe();
read_reg('delegated-arin-extended-latest');    # 修正

join_neighbours();
punch_holes();
optimize();
output();

DBのパスが違うため”ipauth_maker.pl”と”ipcc_maker.pl”のパスを修正

# vi ipauth_maker.pl

32行目付近

print "Saving ultralite IP registry to disk\n";
my $ip = new IO::File "> ../Authority/ipauth.gif"; # 修正
if (defined $ip) {
    binmode $ip;
    print $ip pack("N",time()); # returned by $obj->db_time()
    $tree->printTree($ip);
    $ip->close();
} else {
    die "couldn't write IP registry:$!\n";
}

44 行目付近

print "Saving ultralite country database to disk\n";

open (CC, "> ../Authority/auth.gif") # 修正
    or die ("couldn't create authority database: $!");
binmode CC;
foreach my $country (sort $tree->get_countries()){
    print CC substr(pack('N',$tree->get_cc_as_num($country)),3,1).$country;
}

# vi ipcc_maker.pl

33行目付近

print "Saving ultralite IP registry to disk\n";
my $ip = new IO::File "> ../Country/Fast/ip.gif"; # 修正
if (defined $ip) {
    binmode $ip;
    print $ip pack("N",time()); # returned by $obj->db_time()
    $tree->printTree($ip);
    $ip->close();
} else {
    die "couldn't write IP registry:$!\n";
}

45行目付近

print "Saving ultralite country database to disk\n";

open (CC, "> ../Country/Fast/cc.gif") # 修正
    or die ("couldn't create country database: $!");
binmode CC;
foreach my $country (sort $tree->get_countries()){
    print CC substr(pack('N',$tree->get_cc_as_num($country)),3,1).$country;
}

作成した”db_update”に実行権を与える
# chmod 755 whois_filenames

アップデート実行
# sh whois_filenames

__追記__
2016/06/16 delegated-arin-latestなどがextended-latest形式に変更となっていたため記事の一部を更新しました