Mais um blog inútil.

Coding

Agosto 10, 2010

Arvorezinha em AppleScript

Arquivado em: arvorezinha, coding, lulz, osx — gatuno @ 15:52

Boas tardes a todos,

Ontem à noite, pelas 4 ou 5 e tal da matina, provavelmente devido aos líquidos de Baco e afins, não consegui, por questões várias, colocar aqui a primeira versão da arvorezinha em AppleScript. Como poderá ver o leitor, trata-se de uma linguagem de programação altamente sofisticada e complexa, que não é para qualquer um…
Quem quiser faço um bundle para correr como aplicação :-)

(*
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004

Copyright (C) 2004 Sam Hocevar

Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.

DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

0. You just DO WHAT THE FUCK YOU WANT TO.

*)

set title to “\\m/ 4rV0R321NH4 4ppL3scR1p7 V1.0 H4rD3N3D \\m/”
set sloc to text returned of (display dialog “How many lines?
RFC is lines=5” with title title with icon 1 default answer “5” buttons {“Generate!”} default button 1)
set arv to ""
set j to sloc
set i to 1
try
repeat j times
repeat i times
set arv to arv & “*”
end repeat
set i to i + 1
set arv to arv & "
"
end repeat

display dialog arv with title title buttons {“Save the arvorezinha!”} default button 1
on error
display dialog “7H3R3 w42 4 3RR0r P4RS1N’ 73h NUMb3R 0f l1N32. 7ry 4941n!” with title title buttons {“OK”} default button 1
end try

Finalmente, ao executarmos o script, de acordo com o RFC, obtemos o seguinte resultado:

Salvem a arvorezinha!…

source

Junho 4, 2010

Lost Eden

Arquivado em: coding, serious-business, useless — falso @ 00:11

Olá pessoal.

Eu há uns tempos, quando ainda estava de cama, lembrei-me de um granda jogo dos tempos do DOS, o Lost Eden. A história é sobre um mundo onde os humanos e os dinossauros coexistiam, e eram amigos (alguns), e era bem fixe para a altura!
O jogo era feito de animações em vídeo, género ficheiros FLC feitos no 3D Studio, e incluía altas musicas do grande compositor Stéphane Picq (eu tenho o CD original da banda sonora ;-).

Andei à procura nas internets a ver se alguém já tinha feito o reverse engineer ao jogo, e se já dava para jogar em SO actuais, mas pelos vistos não. A única maneira de o jogar é no DOSBox, mas fica uma beca com frame-skip.
Decidi então, mesmo sabendo que não ia fazer nada de jeito, tentar eu algo.

O jogo vem com alta ficheiro de 431MB chamado EDEN.DAT, fui então primeiro tentar descobrir qual é o conteúdo desse ficheiro.

Este site explica o seguinte:
The EDEN.DAT file begins with 2 bytes which might indicate the number of files contained in the GRAF. Following this number is a series of 25-byte records. Each record is laid out as follows:
bytes 0-11 filename: typically 8.3 DOS filenames, padded with zeroes
bytes 12-15 unknown
bytes 16-19 file size
bytes 20-23 absolute offset of file within GRAF
byte 24 unknown

Então meti mãos à obra, e fiz um script para extrair todos os ficheiros que estão no EDEN.DAT.

#!/opt/local/bin/python
# this script can never fail
import os
import struct

dat = open("EDEN.DAT", "rb")

dat.seek(0)
(total,) = struct.unpack("<H", dat.read(2))
print "O total de ficheiros e: %i" % total

# primeiro 0x2 - 2
# segundo 0x1b - 27
# terceiro 0x34 - 52

for info in range(0,total):
#for info in range(0,1000):
    start = 2+25*info
    
    dat.seek(start)
    filename = str.strip(dat.read(12),'\x00')
    if filename != "":
        print "Filename: %s" % filename
    
        dat.seek(start+16)
        (file_size,) = struct.unpack("<L", dat.read(4))
        print "Tamanho : %i bytes" % file_size
    
        dat.seek(start+20)
        (file_offset,) = struct.unpack("<L", dat.read(4))
        print "Offset: 0x%x" % file_offset
    
        destfn = os.path.join("rip/",filename)
        print "A escrever ficheiro %i: %s " % (info, repr(destfn))
        dat.seek(file_offset)
        dest = open(destfn, "wb")
        dest.write(dat.read(file_size))
        dest.close

dat.close

Consegui então extrair, montes de ficheiros VOC, que são todas as vozes e musicas do jogo, e também vários ficheiros mais ou menos grandes com a extensão HNM e com mais umas buscas nas internets descobri que o HNM é alta formato de video proprietário da já extinta CRYO Interactive Entertainment e que não há nenhum decoder ainda feito. Com essa informação fiquei triste e nunca mais toquei nisto, mas hoje liguei aqui o maczinho e vi aqui isto, e achei que era uma boa coisa para blogar, nem que seja para não perder o código. Espero que tenham gostado.

Fiquem bem, e joguem muito!

Maio 27, 2010

Arvorezinha - HP Precision Architecture (aka PA-RISC aka DEMONIO)

Arquivado em: arvorezinha, assembly, coding, useless — paf @ 16:36

E ca fica mais uma arvorezinha, desta vez numa arquitectura demoniaca.

hpux$ cat arvorezinha.S
        .LEVEL 1.1							; cenas gays do hpux
        .SPACE $PRIVATE$						; o HPPA funciona por spaces, ler arch book
        .SUBSPA $DATA$,QUAD=1,ALIGN=8,ACCESS=31				; pra mais informacoes ou esquizofrenia antecipada
        .SUBSPA $BSS$,QUAD=1,ALIGN=8,ACCESS=31,ZERO,SORT=82
        .SPACE $TEXT$
        .SUBSPA $LIT$,QUAD=0,ALIGN=8,ACCESS=44
        .SUBSPA $CODE$,QUAD=0,ALIGN=8,ACCESS=44,CODE_ONLY
        .IMPORT $global$,DATA
        .IMPORT $$dyncall,MILLICODE
        .IMPORT write,CODE						; eh mais simpatico fazer imports
        .IMPORT exit,CODE
        .IMPORT __main,CODE
        .SPACE $TEXT$
        .SUBSPA $LIT$

        .align 4
STAR
        .STRING "\x2a\x00"
LF
        .STRING "\x0a\x00"
        .SPACE $TEXT$
        .SUBSPA $CODE$

        .align 4
        .NSUBSPA $CODE$,QUAD=0,ALIGN=8,ACCESS=44,CODE_ONLY
        .EXPORT main,ENTRY,PRIV_LEV=3,RTNVAL=GR				; a cena dos privilege levels eh funny
main
        .PROC
        .CALLINFO FRAME=64,CALLS,SAVE_RP,SAVE_SP,ENTRY_GR=3
        .ENTRY
        .CALL
        xor     %r4,%r4,%r4						; aka meter %r4 a zero :)

arewedoneyet
        comib,=,n 5,%r4,kk10xbai					; se %r4 for 5, BAI NAO!
        nop
        xor     %r3,%r3,%r3						; inicializar o counter do segundo loope

letsdothis
        comb,<=,n %r3,%r4,estrela					; se o %r3 for menor ou igual a %r4
        xor %r1,%r1,%r26						; sim, isto eh um nop							

        ldi 1,%r26							; escolher o fd (1 eh stdout)
        ldil LR'LF,%r19							; copiar a stringue com
        ldo RR'LF(%r19),%r25						; paneleirices...
        ldi 1,%r24							; length da stringue
        .CALL ARGW0=GR,ARGW1=GR,ARGW2=GR
        bl write,%r2
        xor %r1,%r2,%r3							; sim, isto eh um nop

        addi    1,%r4,%r4						; incrementar o %r4
        b       arewedoneyet
        shladd %r4,2,%r8,%r15						; sim, isto eh um nop

estrela
        ldi 1,%r26							; ver outro write
        ldil LR'STAR,%r19						; eh a mm merda
        ldo RR'STAR(%r19),%r25
        ldi 1,%r24
        .CALL ARGW0=GR,ARGW1=GR,ARGW2=GR
        bl write,%r2
        add %r13,%r14,%r15						; sim, isto eh um nop

        addi    1,%r3,%r3
        b       letsdothis
        nop								; adivinha...

kk10xbai
        ldi 0,%r26
        .CALL ARGW0=GR
        bl exit,%r2
        shrpw %r8,%r7,8,%r9     ; nop nop nop
        subi,OD  42,%r3,%r12    ; nop nop nop nopppppp! :D
        .EXIT
        .PROCEND
hpux$ gcc arvorezinha.S
*
**
***
****
*****
hpux$

jah agora para esclarecer um pouco certas esquisitisses desta arquitectura, para loadar uma word (32 bits), como todas as instruções têm de ter 32bits eh obvio que nao da para meter um endereço com esse tamanho e ainda gastar 6 bits num opcode. entao o que estes genios da computacao fizeram foi primeiro loadar 21 bits e depois os 11 bits restantes.

tipo ali em cima
ldil LR’STAR,%r19
ldo RR’STAR(%r19),%r25
LR’ saca 21 bits da string STAR para o %r19
RR’ saca os 11 bits que faltam…

digam la, HPPA nao eh uma arquitectura magnifica ? (FUCK NO!)

Maio 25, 2010

Arvorezinha - SPARC!

Arquivado em: arvorezinha, assembly, coding, useless — paf @ 15:10

Btw, esta arch é meio intragável….

solaris$ cat arvore.S
.section  ".rodata1"
.align    4
.L0:
        .ascii           "*\0"
.L1:
        .ascii          "\n\0"

.L2:
        .ascii          "bla\n\0"

        .section        ".text"
        .global         main
main:
        save            %sp,-96,%sp
        mov 0,%g2

arewedoneyet:
        cmp %g2,5       ! comparar com RFC_MAX pois claro, n eh preciso registry pra isto
        be weredonefaggot

        mov 0,%g3       ! inicializar counter1

estrelitas:
        cmp %g3,%g2     ! ah e tal, compara-me a pissa, less or equal?
        ble estrela

        set .L1,%o0     ! meter LF no output register, e mandar printar
        call printf

        inc %g2         ! increasar o counter2
        ba arewedoneyet

estrela:
        set     .L0,%o0 ! printar estrelinha
        call    printf

        inc %g3
        ba estrelitas

weredonefaggot:
        nop
        restore

solaris$ gcc arvore.S -o arvorezinha
solaris$ ./arvorezinha
*
**
***
****
*****
solaris$

Arvorezinha - melhor arquitectura do mundo (Alpha)

Arquivado em: arvorezinha, assembly, coding, useless — paf @ 12:53

Como se lê no subject, fica aqui uma arvorezinha na melhor arquitectura à face do planeta. Em breve na terceira melhor arquitectura à face do planeta…(SPARC)

true64> gcc arvore.S -o arvorezinha
true64> ./arvorezinha
*
**
***
****
*****
true64> cat arvore.S
.data
LF:             .ascii          "\n\0"
GAY:            .ascii          "*"

.text
        .align  4
        .set    noreorder
        .arch   ev4
        .globl  main
        .ent    main

main:
        ldgp    $gp,0($27)		# load ao global pointer
        stq     $26,0($sp)			# inicializar o stack pointer (só naquela)

        lda $10,5                       	# RFC_MAX para o loop principal
        lda $9,0				# counter do loop1

loop1:
        cmpeq $9,$10,$7			# se $9 igual $10, branchar para o final
        bne $7,final

        lda $11,0				# counter para o loop2

loop2:
        cmple $11,$9,$7			# se $11 menor ou igual q $9, estrelar!
        bne $7,estrela

        lda $16,LF				# new line pl0x
        jsr $26,printf
        ldgp $gp,0($26)

        lda $9,1($9)			# uma maneira gay de incrementar
        br loop1

estrela:
        lda     $16,GAY			# printar estrelinha...
        jsr     $26,printf			# é sempre preciso fazer reset ao $gp
        ldgp    $gp,0($26)		# depois de usar uma função

        addq $11,1,$11			# outra maneira gay de incrementar :p
        br loop2

final:
        mov     $31,$0                  # return = 0
        ldq     $26,0($sp)              # limpar a stacka, se bem q nao foi usado mas pronto..
        ret     $31,($26),1             # returnarrrrrrrrr
        .end    main

true64>

Maio 23, 2010

Arvorezinha - REXX

Arquivado em: arvorezinha, coding, useless, windows — falso @ 03:35

Olá de novo, o meu caro amigo cardinal já há uns dias que me tem dito que para eu ser verdadeiramente inútil tinha de fazer uma arvorezinha em AREXX. Fui então pesquisar o que é isso era e descobri que o AREXX é uma implementação para Amiga da linguagem REXX criada pela IBM em 1979 (pelo menos segundo a Wikipedia).
O cardinal disse-me para experimentar o AROS (que é uma implementação do AmigaOS para outras arquitecturas) numa maquina virtual, mas aquilo pareceu-me bues de arcaico. Então fui foi à procura dum interpretador de REXX para Windows, e achei o BREXX (o site é mesmo belo, por isso é que partilhei o urle) e como não há uma sem duas, decidi fazer mais esta arvorezinha hoje, então aqui vai.

/* this script can never fail */
MAX = 5
do i = 1 to MAX by 1
	linha = ""
	do x = 1 to i by 1
		linha = linha || "*"
	end
	say linha
end

E aqui está a prova dos nove.

Arvorezinha - Google Go

Arquivado em: arvorezinha, coding, linux, useless — falso @ 02:54

Olá amigos, estava aqui aborrecido e já a pensar em ir-me deitar porque não tinha series para ver nem nada para fazer, e então lembrei-me que não havia arvorezinha na linguagem de programação Go da Google, então pus mãos à obra, e foi tão simples que até pensei não vir aqui blogar sobre isso, mas como não tinha nada para fazer, aqui vai o sores.

/* this crap can never fail */

package main

import "os"

func main() {
	var RFC_MAX int = 5
	for i := 1; i <= RFC_MAX; i++ {
		for x := 0; x < i; x++ {
			os.Stdout.WriteString("*")
		}
		os.Stdout.WriteString("\n")
	}
}

E a tal pic que toda a gente gosta, como prova!

Maio 16, 2010

Arvorezinha 68K Assembly

Arquivado em: arvorezinha, assembly, coding, useless — falso @ 22:36

Hoje devido aos posts de hoje do falco sobre arvorezinhas ganhei um pouco de moral e fui à procura de arquitecturas que ainda não tivesse feito em assembly e lembrei-me dos Motorola 68K, os que eram usados nos MACs antigos.
Decidi então meter as mãos à obra, e fui procurar um emulador/simulador ou algo do género para este processador e achei o Easy68K que é um três-em-um, Editor, Assembler e Debugger.
Fiquem bem e joguem muito.

* -------------------------------------------can never fail-
* Program    : arvorezinha
* Written by : Pedro de Oliveira
* Date       : 16/05/2010
* Description: Implementação da arvorezinha em 68K assembly 
*-----------------------------------------------------------
        ORG     $1000
START:                          ; first instruction of program

main:
        MOVE.B  #5,d7           ; maximo de linhas/asteriscos
                                ; está a usar o RFC standard 5
        MOVE.B  #0,d5           ; inicializa o counter1 (d5) a 0

ciclo1:
        CMP.B   d5,d7           ; verifica se chegamos o fim
                                ; comparando o counter1 ao maximo
        BEQ     final           ; se for igual salta para o fim
	
        MOVE.B  #0,d6           ; inicializa o counter2 (d6) a 0

ciclo2:
        CMP.B   d5,d6           ; compara o counter1 com o counter2
        BEQ     estrela         ; se for igual
        BLT     estrela         ; ou menor imprime um asterisco
	
        LEA     newline,a1      ; imprime uma newline
        JSR     print
	
        ADD     #1,d5           ; incrementa o counter1
        JMP     ciclo1          ; salta para o ciclo1

estrela:
        LEA     _estrel,a1      ; imprime um asterisco
        JSR     print
	
        ADD     #1,d6           ; incrementa o counter2
        JMP     ciclo2          ; salta para o ciclo2

final:
        MOVE.B  #9,D0
        TRAP    #15             ; halt simulator

print:
        MOVE.B  #14,d0
        TRAP    #15
        RTS

* Variables and Strings

_estrel	DC.B    '*',0
newline DC.B    $0D,$0A,0

        END     START           ; last line of source

Mais três arvorezinhas

Arquivado em: arvorezinha, coding, useless — falco @ 11:19

Em Bash:

#!/bin/bash

ramo="*";
tam="7";
i="1";

while [ $i -lt $tam ]; do
j="1";
while [ $j -lt $i ]; do
printf "$ramo"
j=$[$j+1]
done
printf "\n"
i=$[$i+1]
done

printf "\n\n"

Em Tea:

#!/home/diogo/Tea/tea-3.2.5/bin/tsh

#   Esta é uma arvorezinha escrita em Tea,
#   de acordo com o rfc da arvorezinha praticado
#   em http://www.blol.org/

#   version 0.1

#   This script can never fail!

define arvorezinha ""
define estrelinha "*"
define fiter 1

while { < $fiter 6 } {
define siter 0
while { < $siter $fiter } {
set! arvorezinha [str-cat $arvorezinha $estrelinha]
set! siter [+ $siter 1]
}
set! arvorezinha [str-cat $arvorezinha "\n"]
set! fiter [+ $fiter 1]
}

echo $arvorezinha

Em Tea, com POO

#!/home/diogo/Tea/tea-3.2.5/bin/tsh


#   Esta é uma arvorezinha escrita em Tea,
#   de acordo com o rfc da arvorezinha praticado
#   em http://www.blol.org/

#   version 0.2
#   Changes:
#	* now with an OOP paradigm



#   This script can never fail!



class LitleTree (
    _max_size
    _branch
)

method LitleTree constructor () {
    #Blol.org Arvorezinha RFC COMPLIANT
    set! _max_size 5
    set! _branch "*"
}

method LitleTree PleaseSaveSortelha () {
    echo "Por favor, salva a Sortelha!!!"
    echo "http://vamossalvarsortelha.blogspot.com/"
}

method LitleTree PlantLitleTree () {
    define small_tree
    set! small_tree ""
    define i 0

    while { < $i $_max_size  } {
	set! i [ + $i 1 ]
	define f 0
    	while { < $f $i } {
	    set! f [+ $f 1]
	    set! small_tree [str-cat $small_tree $_branch]
	}
	set! small_tree [str-cat $small_tree "\n"]
    }

    echo $small_tree
}




#serious business:
define litle_tree [ new LitleTree ]
$litle_tree PleaseSaveSortelha
echo "\n"
$litle_tree PlantLitleTree

Março 2, 2010

Multiplicação de polinómios - part ii

Arquivado em: coding, serious-business, useless — dcoder @ 23:42

Viva. Após a maré de degredo que afectou este estimado blog, venho tentar retomar a dignidade e qualidade do mesmo, uma tarefa deveras hercúlea.

Consideremos a multiplicação de polinómios em

$$\mathbb{F}_2[x]$$

. O algoritmo considerado no post anterior é conhecido há milénios e tem uma complexidade quadrática, i.e.,

$$O(n^2)$$

operações para multiplicar dois polinómios de grau n. Este algoritmo será óptimo? Não.

Nos anos 60, foi descoberto o algoritmo de Karatsuba para multiplicar números inteiros em assimptoticamente menos operações. Resumidamente, este algoritmo divide os números a multiplicar na sua parte superior e inferior, e efectua a multiplicação em 3, não 4, multiplicações menores. Por exemplo, para multiplicar 123456 e 789012, dividimos ambos os números a meio: 123, 456, 789 e 012. Obtemos a parte menos significativa do resultado por multiplicar 456*012 = 5472. A parte mais significativa é obtida por 789*123 = 98154. O resto do nosso produto é obtido por efectuar a operação: (123+456)(789+012) - 5472 - 98154 = 360153. O resultado final é 5472 + 10^3*360153 + 10^6*98154 = 97408265472. Podem facilmente verificar que o resultado está correcto.

Este método pode ser aplicado recursivamente aos produtos mais pequenos resultantes de cada passo (divide and conquer). Isto significa que esta recorrência vai precisar de

$$O(n^{\log_2 3})$$

operações para multiplicar dois números. Isto pode parecer irrelevante, mas faz toda a diferença com números grandes (e.g., com mais de 1024 bits.)

O método de Karatsuba não se limita aos inteiros; aplica-se a qualquer anel comutativo. Isto significa que podemos facilmente adaptar este método para multiplicar polinómios. Os truques algébricos para acelerar a multiplicação são uma área extremamente interessante: duas referências relevantes e recomendadas são ‘Multidigit multiplication for mathematicians’ e ‘Faster multiplication in GF(2)[ x ]’.

No caso dos polinómios com coeficientes em {0,1}, i.e.,

$$\mathbb{F}_2[x]$$

, a tarefa é ainda mais simples: a adição é equivalente à subtracção, ambas sendo efectuadas com um simples xor. Implementar este algoritmo em C++ sem operações condicionais é ainda mais simples, dada a natureza recursiva do mesmo:

template<unsigned N>
inline word kmul(word a, word b)
{
	word a0, a1, b0, b1;
	word z0, z1, z2;

	a0 = a&(const word)((1<<(N/2))-1);
	b0 = b&(const word)((1<<(N/2))-1);
	a1 = a>>(const word)(N/2);
	b1 = b>>(const word)(N/2);

	z0 = kmul<N/2>(a0,b0);
	z2 = kmul<N/2>(a1, b1);
	z1 = kmul<N/2>(a0^a1, b0^b1) ^ z0 ^ z2;
	return z0 ^ (z2<<N) ^ (z1<<(N/2));
}

template<>
inline word kmul<1>(word a, word b)
{
	return a&b;
}

Apesar da menor complexidade deste algoritmo, esta implementação não vai ser mais rápida (para todos os tamanhos úteis) do que a do post anterior. Alguém me sabe dizer porquê?