読者です 読者をやめる 読者になる 読者になる

MMACTF 1st 2015 問題 i のwriteup

i言語という独自言語でquineを書け、という問題でした。
変数を持つ場所としてスタックのみが使えるので、その上でどうにかしなければいけません。

.icnファイルが実行できず、手元にいつも使っているパソコンがなかったので、excelvbaインタプリタを書くことにしました。下にコードを上げてます。
あと、.icnの実行方法が結局分からなかったので、どなたか教えてください。


使った命令は、

#23 #42 とか (それぞれ、スタックに23,42を積む)
+-*/ (四則演算)
= (比較。等しければ1を、そうでなければ0を積む)
, (値を数字で出す)
. (値を対応するアスキー文字で出す)
~ (値を-1倍する)
: (値のコピー)
\ (スタックの頭からa番目の値をコピーして積む)
@ (プログラムの実行位置をa文字分移動する)
_ (なにもせずにpopする)
; (正常終了する) 

です。実際の動作は、下のインタプリタを見てください。(多分あってるはず)

quineは、

#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35#46#1~+:#0=#12*@:\#35.,#25~@_:#1=#6*@.#14~@;


になりました。

本質的な部分は、

#46#1~+:#0=#12*@:\#35.,#25~@_
:#1=#6*@.#14~@; 

で、それより前の沢山スタックに値を積んでるところでは、本質的な部分の文字のアスキー値を積んでいます。

まず、

#a#1~+:#0=#b*@:hoge#c~@

とすると、

for(i=a;i>0;i--){ hoge; } 

みたいな動作をしてくれます。(b,cは適当に調節する)
そこで、まず

#46#1~+:#0=#12*@:\#35.,#25~@_

とすると、これはだいたい

for(i=46;i>0;i--){
  printf("#%d", スタックの頭からi番目の値 );
}

みたいなことをやってくれます。
これにより、本質的な部分の直前までの文字(#1#59 ... #35) が、スタックに値を残したまま出力されます。
あとは、

:#1=#6*@.#14~@;

が、だいたい

for(;;){
  p = pop();
  if(p==1)break;
  printf("%c",p);
}

に対応しているので、これで自分自身の文字列が全て出力される、という仕掛けです。


以下が実際に書いて使ったインタプリタです。

Dim A(1000) As Integer
Dim top, pc, isend
Dim s As String
Dim out As String

Sub initi()
 out = ""
 top = 0
 pc = 0
 isend = 0
End Sub

Function push(x)
  A(top) = x
  top = top + 1
  push = A(top - 1)
  Cells(1, top) = x
  
End Function

Function pop()
  Cells(1, top) = ""
  top = top - 1
  pop = A(top)
End Function

Sub instr(x)
  Dim p As Integer, q As Integer
  
  Select Case x
    Case "#"
        push (0)
    Case "="
        p = pop()
        q = pop()
        If p = q Then
            push (1)
        Else
            push (0)
        End If
    Case "*"
        p = pop()
        q = pop()
        push (p * q)
    Case "+"
        p = pop()
        q = pop()
        push (p + q)
    Case "-"
        p = pop()
        q = pop()
        push (q - p)
    Case ":"
        p = pop()
        push (p)
        push (p)
    Case "!"
        p = pop()
        If p = 0 Then
            push (1)
        Else
            push (0)
        End If
    Case ";"
        'MsgBox ("end")
    Case "\"
        p = pop()
        push (A(top - p - 1))
    Case "@"
        pc = pop() + pc
    Case "."
        out = out + Chr(pop())
    Case ","
        out = out + LTrim(Str(pop()))
    Case ";"
        isend = 1
    Case "0"
        push (pop() * 10 + 0)
    Case "1"
        push (pop() * 10 + 1)
    Case "2"
        push (pop() * 10 + 2)
    Case "3"
        push (pop() * 10 + 3)
    Case "4"
        push (pop() * 10 + 4)
    Case "5"
        push (pop() * 10 + 5)
    Case "6"
        push (pop() * 10 + 6)
    Case "7"
        push (pop() * 10 + 7)
    Case "8"
        push (pop() * 10 + 8)
    Case "9"
        push (pop() * 10 + 9)
    Case "~"
        push (pop() * -1)
    Case "_" '_
        pop
    Case Else
        MsgBox ("err! " + x)
        
    End Select
End Sub

Sub run(sss As String)
    Count = 0
    
    For i = 0 To 1000000
        Dim ns As String
        If Len(sss) <= pc Then
            Exit For
        End If
        
            
        ns = Mid(sss, pc + 1, 1)
        Cells(2, 1) = ns
        Cells(2, 2) = pc
        
        instr (ns)
        
        'If pc >= 68 Then
        'pc = pc
        
        'End If
        
         pc = pc + 1
       
    Next i
    
End Sub
'#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35#46#1~+:#0=#12*@:\#35.,#25~@_:#1=#6*@.#14~@;

Sub main()
    initi
    
    Dim se As String
    
    se = "#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35"
   'se = "#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#48#49#35"
   ' se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95#64#126#49#51#35#44#46#53#51#35#92#58#64#43#50#49#35#42#50#49#35#126#33#61#48#35#58#43#126#49#35#55#53#35"
    'se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95#64#126#49#51#35#44#46#53#51#35#92#58#64#43#50#49#35#42#50#49#35#126#33#61#48#35#58#43#126#49#35#48#49#35"
    
    'se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95"
    'se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95#64#126#49#51#35#44#46#53#51#35#92#58#64#43#50#49#35#42#50#49#35#126#33#61#48#35#58#43#126#49#35#48#49#35#57#53#35#52#54#35#54#50#49#35#55#53#35#57#52#35#53#51#35#54#52#35#52#54#35#51#52#35#52#53#35#53#51#35#50#52#35#52#53#35#53#51#35#54#50#49#35#51#51#35#49#54#35#57#52#35#53#51#35#56#53#35#53#57#35#52#54#35#54#50#49#35#57#52#35#49#53#35#53#51#35#52#52#35#54#52#35#51#53#35#49#53#35#53#51#35#50#57#35#56#53#35#52#54#35#51#52#35#48#53#35#57#52#35#53#51#35#50#52#35#48#53#35#57#52#35#53#51#35#54#50#49#35#51#51#35"
    
    'se = "#1#56#35#49#48#35#49#126#43#58#35#48#61#33#126#35#49#50#42#35#49#50#43#64#58#92#35#51#53#46#44#35#51#49#126#64#95#58#35#49#61#33#126#35#54#42#35#54#43#64#46#35#49#57#126#64#59"
    'se = "#1#12#12#12#14#13#16#15#17#19#18#25#1#38"
    'se = se + "#57#1~+:#0=!~#12*#12+@" 'forのための。
    se = se + "#46#1~+:#0=#12*@" 'ないなら0なので。
    se = se + ":\#35.,#25~@" 'ループ1
    'run (se)
    'MsgBox (out)
    se = se + "_:#1=#6*@"
    se = se + "."
    se = se + "#14~@"
    se = se + ";"
    Cells(3, 1) = se
    run (se)
    'MsgBox (out)
    Cells(4, 1) = out
    
    Dim cs As String
    cs = ""
    ccs = ""
    
    For j = (Len(se) - 43) To Len(se)
        nc = Mid(se, j, 1)
        cs = ("#" + LTrim(Str(Asc(nc)))) + cs
        ccs = ccs + nc
    Next j
    
    Cells(5, 1) = cs
    Cells(7, 1) = Len(cs)
    Cells(6, 1) = ccs
    Cells(8, 1) = Len(se)
    
End Sub