quarta-feira, 15 de julho de 2009

ICFP2009 - decodificando o programa

Linguagens funcionais são fantásticas quando sabemos aproveitá-las. Uma das coisas mais legais de se fazer em uma linguagem funcional é outra linguagem! Na tarefa do ICFP Contest 2009, uma das etapas é construir a VM para executar o binário fornecido.

Poderíamos decodificar as instruções apenas na hora de executá-las, mas em Haskell (ou qualquer linguagem funcional), é bem mais simples aplicar um map na lista de Word32 lida, convertendo-a em uma lista de dados do tipo instrução.

Começamos isso definindo o tipo:

module OBFProgram where

import Data.Word
import Data.Bits
import OBFData


type OBFProgram=[(Int,OBFInst)]

data OBFInst= Add !Int !Int |
Sub !Int !Int |
Mult !Int !Int |
Div !Int !Int |
Out !Int !Int |
Phi !Int !Int |
Noop |
Cmpz CmpzType !Int |
Sqrt !Int |
Copy !Int |
Inp !Int
deriving (Show,Eq)

data CmpzType= LTZ |
LEZ |
EQZ |
GEZ |
GTZ
deriving(Show, Enum,Eq)

Haskell é uma linguagem de avaliação tardia, mas nem sempre isso é bom. O map utilizado em decode só vai ser executado quando pegarmos o primeiro item da nova lista. Mas se cada elemento dentro do map também for tardio, significa que iremos ler o arquivo também nessa primeira execução, o que pode tornar tudo muito lento. Outro problema é que, a medida que vamos "acumulando" execuções atrasadas (thunks), elas vão se juntando em memória, criando um enorme bloco. Para reduzir isso, coloquei os ! antes de cada elemento dentro da declaração do tipo. Esse ! (também conhecido como bang) identifica um placeholder onde o dado só pode entrar depois de computado. Desta forma, quando crio, por exemplo, Add x y, a execução dos thunks que geram x e y vai ser forçada, e o elemento irá guardar efetivamente um inteiro em cada uma das posições.

decode::[Word32]-> OBFProgram
decode x=filter ((/=Noop).snd) (zip [0..] (map decodeInstruction x))

O restante do código é bastante básico. Mastigamos os bits de cada Word32 e, utilizando case, convertemos cada elemento da lista em uma instrução.

decodeInstruction::Word32->OBFInst
decodeInstruction x=
case opcode of
0 -> decodeSType par1 par2
1 -> Add par1 par2
2 -> Sub par1 par2
3 -> Mult par1 par2
4 -> Div par1 par2
5 -> Out par1 par2
6 -> Phi par1 par2
where
opcode=fromIntegral( (x `shiftR` 28) .&. 15 )
par1 =fromIntegral( (x `shiftR` 14) .&. 16383 )
par2 =fromIntegral( x .&. 16383 )

decodeSType::Int->Int->OBFInst
decodeSType par1 par2=
case opcode of
0->Noop
1->Cmpz (toEnum imm) par2
2->Sqrt par2
3->Copy par2
4->Inp par2
where
opcode = (par1 `shiftR` 10).&.15
imm = (par1 `shiftR` 7).&. 7

No próximo post, vou apresentar a minha versão da representação dos dados. Essa sim, vai surpreender.

Nenhum comentário:

Postagens populares