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

Scalaでライフゲーム

Scalaライフゲームを実装した。

import scala.collection.mutable.ArrayBuffer
import scala.swing._
import scala.swing.event._
import java.awt.{Color,Graphics2D,BasicStroke}
import java.awt.geom._
import java.awt.image.BufferedImage
import scala.collection.mutable._
import scala.math._

class Environment(val sqnum:Int){
  val cells=Array.ofDim[Int](sqnum,sqnum)
  val cells0=Array.ofDim[Int](sqnum,sqnum)
  val queue = new Queue[(Int,Int)]
  def apply(x:Int,y:Int)=cells(x)(y)
  def next={
    for (i<- 0 until sqnum){
      for (j<- 0 until sqnum){
        cells0(i)(j)=cells(i)(j)
      }
    }
    for (i <- 0 until sqnum){
      for (j <- 0 until sqnum){
        val surroundLives=getSurrounding(i,j).map({case(x,y)=>cells0(x)(y)}).sum
        if (cells0(i)(j)==1){
          if (surroundLive<=1)cells(i)(j)=0
          else if (surroundLive<=3)cells(i)(j)=1
          else cells(i)(j)=0
        }else{
          if(surroundLives==3){
            cells(i)(j)=1
          }
          else cells(i)(j)=0
        }
        if (cells0(i)(j)!=cells(i)(j)){
          queue.enqueue((i,j))
        }
      }
    }
    def getSurrounding(x:Int,y:Int):List[(Int,Int)]={
      val sur=Array.fill[Boolean](3,3){true}
      sur(1)(1)=false
      if(y==sqnum-1){
        for (i<- 0 until 3) sur(i)(2)=false
      }
      if(y==0){
        for (i<- 0 until 3) sur(i)(0)=false
      }
      if(x==sqnum-1){
        for (i<- 0 until 3) sur(2)(i)=false
      }
      if(x==0){
        for (i<- 0 until 3) sur(0)(i)=false
      }
      (for (i <- 0 until 3) yield (for (j<- 0 until 3 if sur(i)(j)) yield (x+i-1,y+j-1)).toList).reduceLeft(_:::_)  
    }
  }
  def randoms={
    for (i<-0 until sqnum){
      for (j<-0 until sqnum){
        if(floor(random*3).toInt%4==0){
          cells(i)(j)=1
        }
      }
    }
  }
  def bornOfNewCell(x:Int,y:Int)=cells(x)(y)=1
  def terminationOfAll=for (i<- 0 until sqnum) {for (j<- 0 until sqnum) {cells(i)(j)=0;queue.enqueue((i,j))}}
}

class Canvas (val env:Environment) extends Component{
  val imgBuffer = new BufferedImage(320,320,BufferedImage.TYPE_INT_RGB)
  preferredSize = new Dimension(320,320)
  listenTo(mouse.clicks)
  reactions+={
    case MouseClicked(_,p,_,_,_)=>mouseClick(p.x,p.y)
  }
  private def correspondCanvasToEnv:(Int,Int,Int,Int)={
    val d = size
    val squareSide=d.height min d.width
    val x0 = (d.width-squareSide)/2
    val y0 = (d.height-squareSide)/2
    (squareSide,x0,y0,squareSide/env.sqnum)
  }
  private def mouseClick(cx:Int,cy:Int){
    val (_,cx0,cy0,wid)=correspondCanvasToEnv
    val (ex,ey)=((cx-cx0)/wid,(cy-cy0)/wid)
    env.bornOfNewCell(ex,ey)
  }
  override def paintComponent(g:Graphics2D){
    val bg=imgBuffer.getGraphics
    val (_,cx0,cy0,wid)=correspondCanvasToEnv
    g.setRenderingHint(
        java.awt.RenderingHints.KEY_ANTIALIASING,
        java.awt.RenderingHints.VALUE_ANTIALIAS_ON)
    while(!env.queue.isEmpty){
      val (x,y)=env.queue.dequeue()
      if (env(x,y)==1)bg.setColor(Color.GREEN)
      else bg.setColor(Color.BLACK)
      bg.fillRect(cx0+x*wid,cy0+y*wid,wid,wid)
    }
    g.drawImage(imgBuffer,0,0,null)
  }
}
class Lifegame (val env:Environment) extends MainFrame{
  title="LIFEGAME"
  resizable=false
  val canvas=new Canvas(env)
  contents=new BoxPanel(Orientation.Vertical){
    contents+=canvas
    contents+=new BoxPanel(Orientation.Horizontal){
      contents+=Button("All Clear"){env.terminationOfAll}
      contents+=Button("Random"){env.randoms}
      contents+=Button("Next"){env.next;canvas.repaint}
    }
  }
  Timer(300){
    env.next
    canvas.repaint
  }
}
object Timer{
  def apply(interval:Int,repeats:Boolean=true)(op: => Unit){
    val timeOut=new javax.swing.AbstractAction(){
      def actionPerformed(e:java.awt.event.ActionEvent)=op
    }
    val t=new javax.swing.Timer(interval,timeOut)
    t.setRepeats(repeats)
    t.start()
  }
}
object Main{
 def main(arg:Array[String]){
   val env=new Environment(40)
   env.terminationOfAll
   val ui=new Lifegame(env)
   ui.visible=true
 }
}


[追記]
後にScalaでのライフゲームの実行例を調べてみたらこのような実装があった。
qiita.com


リストの境界部分へとアクセスするときにIndexOutOfBoundsExceptionを使って処理していてとても参考になった。
例外を上手に活用したことがないので今後は意識していきたい。

Scalaで波のシュミレーション

scalaで波のシュミレーションを行った。

import scala.swing._
import scala.swing.event._
import java.awt.image.BufferedImage
import java.awt.{Color,Graphics,Graphics2D,BasicStroke}
import java.awt.geom._

class Field(val step:Int){
  val s=0.1f
  val u0=Array.ofDim[Float](step,step)
  val u1=Array.ofDim[Float](step,step)
  val u2=Array.ofDim[Float](step,step)
  val queue=new scala.collection.mutable.Queue[(Int,Int)]
  val maxAmplitude=500.0f
  for (i<- 0 until step) for (j <- 0 until step) queue.enqueue((i,j))
  def apply(x:Int,y:Int)=u0(x)(y)
  def init={
    for (i <- 0 until step){
      for (j <- 0 until step){
        u0(i)(j)=0
        u1(i)(j)=0
        u2(i)(j)=0
      }
    }
  }
  def newWaveSource(x:Int,y:Int,amplitude:Float=250.0f)= u0(x)(y)=amplitude
  def calculate={
    
    for (i <- 0 until step){
      for (j <- 0 until step){
        u2(i)(j)=u1(i)(j)
        u1(i)(j)=u0(i)(j)
      }
    }
    for (i <- 0 until step){
      u0(0)(i)=0
      u0(step-1)(i)=0
      u0(i)(0)=0
      u0(i)(step-1)=0
    }
    for (i <- 1 until step-1){
      for ( j <- 1 until step-1){
        val w=2*u1(i)(j)-u2(i)(j)+s*s*(u1(i-1)(j)-2*u1(i)(j)+u1(i+1)(j)+u1(i)(j-1)-2*u1(i)(j)+u1(i)(j+1))
        if(w!=u0(i)(j))queue.enqueue((i,j))
        u0(i)(j)=w
      }
    }
  }
}
class Canvas(val field:Field) extends Component{
  preferredSize = new Dimension(320,320)
  val imgBuf=new BufferedImage(320,320,BufferedImage.TYPE_INT_RGB)
  listenTo(mouse.clicks)
  reactions+={
    case MouseClicked(_,p,_,_,_)=>mouseClick(p.x,p.y)
  }
  private def mouseClick(cx:Int,cy:Int){
    val (squreSide,cx0,cy0,wid)=squareGeometry
    val (fx,fy)=((cx-cx0)/wid,(cy-cy0)/wid)
    List((0,0),(1,1),(1,0),(0,1)).foreach({case(px,py)=>
    field.newWaveSource(fx+px,fy+py)
    })
    
  }
  private def squareGeometry:(Int,Int,Int,Int)={
    val d = size
    val squareSide=d.height min d.width
    val x0 = (d.width-squareSide)/2
    val y0 = (d.height-squareSide)/2
    (squareSide,x0,y0,squareSide/field.step)
  }
  private def amplitudeWaveToColor(amp:Float,max:Float):Color={
    var p=amp/max
   
    if(p<0){
      if(p < -1)p = -1
      new Color((255*(-p)).toInt,(255*(1+p)).toInt,0)
      
    }else{
      if (p>1)p=1
      new Color(0,(255*p).toInt,(255*(1-p)).toInt)
     
    }
  }
  
  override def paintComponent(g:Graphics2D){
    val gb=imgBuf.getGraphics
    g.setRenderingHint(
        java.awt.RenderingHints.KEY_ANTIALIASING,
        java.awt.RenderingHints.VALUE_ANTIALIAS_ON)
    val (squareSide,x0,y0,wid)=squareGeometry
    while(!field.queue.isEmpty){
      val (x,y)=field.queue.dequeue()    
      gb.setColor(amplitudeWaveToColor(field(x,y),field.maxAmplitude))
      gb.fillRect(x0+x*wid,y0+y*wid,wid,wid)
    }
    g.drawImage(imgBuf,0,0,null)
  }
}
class Wave(val field :Field,val updateInterval:Int) extends MainFrame{
  private def restrictHeight(s:Component){
    s.maximumSize = new Dimension(Short.MaxValue,s.preferredSize.height)
  }
  title="Water surface"
  resizable=false
  val canvas=new Canvas(field)
  contents=canvas
  Timer(updateInterval){
    field.calculate
    canvas.repaint
  }
}
object Timer{
  def apply(interval:Int,repeats:Boolean=true)(op: => Unit){
    val timeOut=new javax.swing.AbstractAction(){
      def actionPerformed(e:java.awt.event.ActionEvent)=op
    }
    val t=new javax.swing.Timer(interval,timeOut)
    t.setRepeats(repeats)
    t.start()
  }
}
object Main{
  def main(args:Array[String]){
    val field=new Field(320)
    val ui=new Wave(field,100)
    ui.visible=true
  }
 }

値を更新するごとに全面を書き換えるのは無駄な気がしたので値が変わったもののみを書き換えることにした。これはQueueとBufferedImageを用いることで実装した。また、波の振幅を色を用いて表現する上手い式が思いつかなかったのでやっつけで作った。(amplitudeWaveToColor)

以下のサイトを参考にした。
Processingでシミュレーション~波動方程式 - Qiita

java - How to draw an image over another image? - Stack Overflow

Scala Documentation -- GUI Programming

Twitter4j,kuromojiを使ってみた

Scalaの練習のためにtwitter4jとkuromojiを使ってプログラムを書いた。
指定したユーザーの直近50ツイートの中に含まれる単語の頻度を求めた。

import twitter4j._
import com.atilika.kuromoji.ipadic.Token
import com.atilika.kuromoji.ipadic.Tokenizer
import com.atilika.kuromoji.ipadic.Tokenizer.Builder
import scala.collection.JavaConverters._
import scala.collection.mutable.Buffer


object Main {
   def getTweets(twitter:Twitter,userName:String,tweetCount:Int):Buffer[Status]={
    val pageSize=20
    val pageCount=(tweetCount+pageSize-1)/pageSize
    ((for (i <- 1 to pageCount) yield twitter.getUserTimeline(userName,new Paging(i,pageSize)).asScala)).reduceLeft(_++_).take(tweetCount)
  }
  def getFrequencyOfWord(samples:List[String],map:Map[String,Int],tokenizer:Tokenizer):Map[String,Int]={
    val typeSpeech=List("名詞","動詞","副詞","形容詞")
    (for (sample<-samples) yield for (token<-tokenizer.tokenize(sample).asScala if typeSpeech.exists(_==token.getPartOfSpeechLevel1))yield token.getBaseForm).reduceLeft(_++_).foldLeft(map){(acc,e)=>acc+(e->(acc.getOrElse(e,0)+1))}
  }
  def main(args:Array[String]){
    val twitter=TwitterFactory.getSingleton
    val user=twitter.verifyCredentials
    val tokenizer=new Tokenizer
    print(getFrequencyOfWord(getTweets(twitter,"@",50).map(_.getText).toList,Map.empty[String,Int],tokenizer))
  }
}

Mavenのpom.xml(dependencies)は以下の通り。

<dependencies>
  	<dependency>
  		<groupId>org.twitter4j</groupId>
  		<artifactId>twitter4j-core</artifactId>
  		<version>4.0.6</version>
  	</dependency>
  	<dependency>
    	<groupId>com.atilika.kuromoji</groupId>
    	<artifactId>kuromoji-core</artifactId>
    	<version>0.9.0</version>
	</dependency>
	<dependency>
    	<groupId>com.atilika.kuromoji</groupId>
    	<artifactId>kuromoji-ipadic</artifactId>
    	<version>0.9.0</version>
	</dependency>
  </dependencies>

参考にさせていただいたサイトは以下の通り
Scalaでテキストマイニングしてみた | blue engineer blog
Design Recipe 別館 Blog - Scala と Ruby で単語の出現頻度を調べて多い順にソートする
Twitter4Jを使ったら10分でつぶやきJavaプログラムが作れました! ~NetBeans編~ - Challenge Java EE !

Scalaでbrainfuck

何となくScalabrainfuckの処理系を実装した。

package brainfuck

sealed trait Inst
case object PINC extends Inst
case object PDEC extends Inst
case object INC extends Inst
case object DEC extends Inst
case object OUT extends Inst
case object IN extends Inst
case object NOP extends Inst
final case class JZ(dst:Int) extends Inst
final case class JNZ(dst:Int) extends Inst

class TM(val Ops:Array[Inst]){
  var IP:Int=_
  val memory:Array[Byte]=new Array[Byte](30000)
  var pointer:Int=_
  var Op:Inst=_
  
  def fetch={
    Op=Ops(IP)
    IP+=1
  }

  def decode={}

  def execute={
    Op match{
      case PINC =>pointer+=1
      case PDEC =>pointer-=1
      case INC  =>memory(pointer)=(memory(pointer)+1).asInstanceOf[Byte]
      case DEC  =>memory(pointer)=(memory(pointer)-1).asInstanceOf[Byte]
      case OUT  =>print(new String(Array(memory(pointer)),"UTF-8"))
      case IN   =>{
        var a=System.in.read()
        if (a == -1) IP = -1
        memory(pointer)=a.toByte
      }
      case JZ(dst) => if (memory(pointer)==0) IP=dst
      case JNZ(dst)=> if (memory(pointer)!=0) IP=dst
      case NOP=>{}
    } 
  }
  def run=while (IP<Ops.size && IP>=0){fetch;decode;execute}
}

object Compiler{
  def compile(code:String):Array[Inst]={
    var ops:Array[Inst]=Array.empty
    var stack=new scala.collection.mutable.Stack[Int]
    code.zipWithIndex.foreach{ 
      case(c:Char,index:Int)=>{
        c match {
          case '>' =>ops=ops:+PINC
          case '<' =>ops=ops:+PDEC
          case '+' =>ops=ops:+INC
          case '-' =>ops=ops:+DEC
          case '.' =>ops=ops:+OUT
          case ',' =>ops=ops:+IN
          case '[' =>{
            ops=ops:+NOP
            stack.push(index)
          }
          case ']' =>{
            val src=stack.pop
            ops(src)=JZ(index+1)
            ops=ops:+JNZ(src+1)
          }
        }
      }
    }
    ops
  }
}

何せscalaを勉強し始めたのが一昨日だけにもっと上手い書き方があるような気がしてならない。
特に

  • 命令セットの列挙型としての扱い方
  • IntとByteの変換

の部分。

ksnctf,Q31

Q31 KanGacha
ksnctf.sweetduet.info
length extension攻撃(伸長攻撃)
参考
Everything you need to know about hash length extension attacks » SkullSecurity
このサイトを参考にした。
このサイトではMD5を例にとり伸長攻撃を実践していた。
これを例にしsha512の場合のプログラムを書こうとしたが失敗したのでhash_extenderというツールを使うことにした。

Cookieにセットされているshipとsignatureをhash_extenderに投入して出てきたshipとsignatureでburp suiteでインタセプトした正常な値を置き換える。flagがゲットできる。

ksnctf、今日は2問

Q13 proverb
ksnctf.sweetduet.info

シンボリックリンク攻撃
実行ファイルとflagの両方のシンボリックリンクを/tmpのサブディレクトリに作ってそこで実行。
flagが出力される。

Q21 Perfect Cipher
ksnctf.sweetduet.info

メルセンヌ・ツイスタ
メルセンヌツイスタで作った乱数を鍵としてファイルのバイナリの排他的論理和を取る暗号の解読。
メルセンヌツイスタはseedが同一な場合途中の連続する624個の乱数がわかってしまえば他の全ての乱数を計算することができるのでそのことを利用してflagの方の鍵を求める。
こうして求めた鍵を使って暗号化されたflagの画像ファイルを復号出来たのだが、画像として表示できなかった。
しばらく悩みながらなんとなく復号された画像ファイルをバイナリエディタで眺めると、FLAG_…の文字列があった。

久しぶり

久しぶりにksnctfを解いた。
Q7
ksnctf.sweetduet.info

ぱっと見するとC言語だが空白として隠されているのがWhitespaceという言語。
ネットで調べて出てきたインタプリタに突っ込む。
Whitespace Interpreter written in JavaScript

変換されたJavascriptのコードを適当に読み取りpythonで再現した。

#!/usr/bin/python

stack=[]



stack.append(70)
stack.append(70)
print chr(stack.pop()),
stack.append(6)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(11)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(6)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(24)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(26)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(40)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(25)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(36)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(66)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(16)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(14)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(14)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print chr(stack.pop()),
stack.append(27)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(5)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(29)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(4)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(4)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(28)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(22)
stack.append(stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(34)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),
stack.append(55)
stack.append(-stack.pop() +stack.pop())
stack.append(stack[len(stack) - 1])
print  chr(stack.pop()),

フラグをゲット。

Q34
ksnctf.sweetduet.info
Are you human ?
Yes,I'm human
大量の画像が入ったpngの画像とリードソロモン符号のエンコードスクリプトが与えられる。
画像には一枚あたり32個(最後の一個だけ10個)の英数字(というか16進数で使われる文字)が入っている。
この00000000.pngを見てみるとjpegのSOIと思わしき並びがあったので、これらを全てつなげたものが、与えられたスクリプトによってエンコードされたファイルであると思われる。
とりあえず白黒にしてメディアンフィルタにかけた上でtesseractで文字を読み取ろうと試みたところ、7571ファイル中3000ファイルくらいしか32文字ちょうどを読み取ることが出来なかった。
仕方がないので自分でノイズ(線)を消すプログラムを書くと、32文字ちょうどを読み取れなかったのは15ファイルほどになったので、それらを手作業で文字に落とし込んだ。
これらの16進数をバイナリにして一つのファイルに書き込んだ。
最後にこれをリードソロモン符号のデコードを試みた。
ネットで調べたところreedsoloというライブラリが出てきたのでこれを用いた。
画像64バイトに対して冗長191バイトであることが読み取れたのでこれらをくっつけてデコードした。
すると、エラーを吐いた。どうやら誤りが多すぎたみたいだ。多分画像データから16進数の文字を適切に読み取れなかったのだろう。
新しく画像のノイズを消すプログラムを書くのもめんどうだったのでとりあえず放置。