Hatena::ブログ(Diary)

菊やんの雑記帳

2007-12-18 pointer-freeなC言語

[] pointer-free な C 言語はチューリング完全03:36  pointer-free な C 言語はチューリング完全か - 菊やんの雑記帳 を含むブックマーク

ってのが、id:mame っちのところにあったので似非実装


char code[1024];
char input[1024];

struct V {
#define REEVAL 0
#define RETURN 1
#define COMPLETE 2
  int state;
  int value;
};

/*
 * ret_step ステップ実行した後の
 * ret_cursor の値を返す。
 */
int re_eval(int ret_step, int ret_cursor);

/*
 * ret_step ステップ実行して結果を返す
 * step はこれまで実行したステップ数
 * pc は実行を開始するコード位置
 * cursor は現在のカーソル位置
 * cell は現在のカーソル位置の値
 * ipos は入力位置
 *
 * i) ret_step == -1 の場合
 *   プログラムは最後まで実行され
 *   { state = COMPLETE; value = 0} が返される。または終了しない。
 * ii) ret_step >= の場合
 *   プログラムは ret_step まで実行される。
 *   a) 実行し終わったときのカーソルが ret_cursor と一致した場合
 *      { state = RETURN; value = カーソル位置の値 }
 *   b) 実行し終わったときのカーソルが ret_cursor と異なっている場合
 *      { state = REEVAL; value = step }
 *
 */
struct V eval(int step, int ret_step, int ret_cursor, int pc, int cursor, int cell, int ipos)
{
  int step_save = step;
  struct V v;

  /*
   * ret_step まで実行しなくても
   * 値は0であることが確定している。
   */
  if (ret_step >= 0 && ret_step <= ret_cursor) {
    v.state = RETURN;
    v.value = 0;
    return v;
  }
  
  while (ret_step == -1 || step < ret_step) {
    switch (code[pc]) {
    case '+': cell++; pc++; step++; break;
    case '-': cell--; pc++; step++; break;
    case '<': pc++; step++;
      {
        /* カーソルを左に移動する前に
         *  step_save での cursor-1 が必要
         */
        int left_cell = re_eval(step_save, cursor-1);
        return eval(step, ret_step, ret_cursor, pc, cursor-1, left_cell, ipos);
      }
    case '>': pc++; step++;
      {
        /* カーソルを右に移動する前に
         *  step_save での cursor+1 が必要
         */
        int right_cell = re_eval(step_save, cursor+1);
        return eval(step, ret_step, ret_cursor, pc, cursor+1, right_cell, ipos);
      }
    case '.': pc++; step++;
      {
        v = eval(step, ret_step, ret_cursor, cursor, cell, ipos, exec);
        if (v.state == COMPLETE) {
          putchar(cell);
        }
        return v;
      }
    case ',': pc++; step++;
      {
        cell = input[ipos++];
        break;
      }
    case '[': pc++; step++;
      {
        if (!cell) {
          int n;
          for (n = 1; n > 0;) {
            if (code[pc] == '[') n++;
            if (code[pc] == ']') n--;
            pc++;
          }
        }
        break;
      }
    case ']': step++;
      {
        int n;
        for (n = 1; n > 0;) {
          pc--;
          if (code[pc] == '[') n--;
          if (code[pc] == ']') n++;
        }
      }
    case 0:
      {
        if (ret_step == -1) {
          v.state = COMPLETE;
          v.value = 0;
        } else {
          v.state = REEVAL;
          v.value = step_save-1;
        }
        return v;
      }
    default: pc++; step++; break;
    }
  }
  if (ret_cursor == cursor) {
    v.state = RETURN;
    v.value = cell;
  } else {
    v.state = REEVAL;
    v.value = step_save-1;
  }
}

int re_eval(int ret_step, int ret_cursor)
{
  struct V v;
  for (;;) {
    v = eval(0, ret_step, ret_cursor, 0, 0, 0, 0);
    if (v.state == RETURN)
      return v.value;
    ret_step = v.value;
  }
}

int main()
{
  read_code();
  read_input();
  eval(0, -1, 0, 0, 0, 0, 0);
  return 0;
}

コンパイルすらしてない。

va_arg 使うよりはましだが、これじゃ不完全。

現在のカーソル位置の値だけおぼえといて、隣に移動したときは最初から実行しなおして、隣の値を思い出してから実行する。

2007-05-04 定数除算

[] 21:02 定数除算 - 菊やんの雑記帳 を含むブックマーク

VC++が定数による除算を乗算に変換する最適化をしてるのは、吐いたコードを見たことある人なら知ってることだと思うけど、なんとなく

http://www.wikihouse.com/x86clocker/index.php?plugin=attach&refer=%B2%E1%B5%EE%A5%ED%A5%B0&openfile=x86%CC%BF%CE%E1%A4%CE%BD%EA%CD%D7%A5%AF%A5%ED%A5%C3%A5%AF%B7%D7%C2%AC%A5%B9%A5%EC.html

このスレの400を見てて、確かに正確な変換方法は知らないので考えてみる。

mov eax, 40140141h ; r=esi/819とおく。esi=819r 
mul esi ;edx=205r 
sub esi, edx ;esi=614r 
shr esi, 1 ;esi=307r 
add esi, edx ;esi=512r 
shr esi, 9 ;esi=r 
これなんか、esi/=819; だぜ。人智を超えている。まあ、人智の生んだコンパイラだが。 
40140141hは2^32*205/819で、205の大きさで精度を上げて9bitシフトで仕上げている。 
一般的な式を出したいな。 

まず、このコードについてるコメントは間違ってるので正確に書くと

mov eax, 40140141h ; r = esi/819とおく。esi = 819r + rem (0<=rem<819)
mul esi            ; edx = 205r + e (0<=e<=205)
sub esi, edx       ; esi = (819r + rem) - 205r - e = 614r + rem - e
shr esi, 1         ; esi = 307r + (rem - e)/2 
add esi, edx       ; esi = (307r + (rem - e) / 2) + 205r + e= 512r + (rem + e) / 2 
shr esi, 9         ; esi = r + ((rem + e) / 2)/512 = r 

のようにちゃんと余りも書かないとだめ。esi = 2^32 - 1 - 2^32 % 819 のときに e = 205 になる。

e + rem < 1024 なのがポイント。

とりあえず符号なしとする。除数をMとして(3<=M<2^32)とする。

Mで割る代わりにTを掛けるようにしたいので、f(M) = F(M) * 2^32 を M で割った商+1を T とすることを考える

この f がみたすべき条件を考えると

  f(M) = (T-1) * M + R,   (0 <= R < f(M))

ここで、Tは32ビットに収まってないといけないので

  f(M) < M * (2^32 - 1)
  F(M) <= M - 1

被除数をm(0<=m<2^32)として除算の結果を、m = k * M + r とする。

実際に T を掛けてみると、

  m * T = m * ((f(M) - R) div M + 1)
        = (m * (f(M) - R + M)) div M
        = k * f(M) + floor((r * f(M) + m * (M - R)) / M)

となる。

(M - R) >= 0 より

  floor((r * f(M) + m * (M - R)) / M) >= 0

は常に成立している。さらに

  floor((r * f(M) + m * (M - R)) / M) < f(M) + 2^32

も成立する。よって

 k * F(M) <= m * T div 2^32 <= (k+1) * F(M)

である。

後ろの等号が成立しない場合に制限したければ

  floor((r * f(M) + m * (M - R)) / M) < f(M)
  <=> f(M)/(M - f(M) mod M) > m / (M - m mod M)

をみたさなければならない。

右辺は m = 2^32-1 か m = 2^32-1-2^32%M で最大値をとる。

F(M)は2の冪になってるのが望ましいので、M-1以下の2の冪でこれを満たすものを見つければよい。

見つからない場合は、

a < M < 2*a となる2の冪 a に対して、F(M) = 2 * a - M とする。このときは後ろの等号が成立するかもしれないので

 s := m * T div 2^32
 x := s - k * F(M)
 y := m - s = k * (M - F(M)) + r - x = k * 2 * (M - a) + r - x
 z := y div 2 = k * (M - a) + (r-x) div 2
 w := z + s = k * a + (r - x) div 2 + x = k * a + (r + x) div 2

と計算すると、ちょうど

  0 <= x <= F(M) = 2 * a - M
  0 <= r < M
  0 <= r + x < 2 * a
  0 <= (r + x) div 2 < a

となり、w / a = k を得る。

2007-01-02 The 19th IOCCC Competition

[] 04:41 The 19th IOCCC Competition - 菊やんの雑記帳 を含むブックマーク

IOCCCが始まったようです。

参加しようと思っていながら、いつの間にか終わっていたってのを数年間続けていたのですが、

今回は真面目にアンテナでチェックしてたので参加できそう。

2006-12-02 sizeof

[]すっかり忘れてた 20:23 すっかり忘れてた - 菊やんの雑記帳 を含むブックマーク

この前の問題はC++では解けません。なぜならC++では「式の中で新しい型を定義してはいけない」と決まってるからです。大ヒントだね。

OzyOzy 2006/12/02 21:14 わかりましたー!どもです!!

2006-11-21

[]某所にも書いたけど 05:00 某所にも書いたけど - 菊やんの雑記帳 を含むブックマーク

int main() {
  int A = 1; 
  { 
    sizeof(EXP); 
    printf("%d\n", A); 
  }
  return 0;
}

が、100を出力するような式EXPは何か?

簡単だよね(ぉ

マクロとか使っちゃだめだよ

firewoodfirewood 2006/12/01 23:02 1);(A=100
は、ナシですか?

OzyOzy 2006/12/02 10:51 sizeof演算子を使うと、不思議な挙動をするのは実際にコードを書いてわかったのですが、それをコントロールするには至りませんでした(´ω`)
解説orヒントぷりーず!!!