Partial evaluation and tracing example 1 in python

# Partial Evaluation
# http://morepypy.blogspot.com/2012/01/comparing-partial-evaluation-and.html

blocks = {
  "power": ("op1", "res", "same", ("const", 1),
             ("if", "y", "power_rec", "power_done")),
  "power_rec": ("op2", "res", "mul", ("var", "res"), ("var", "x"),
                ("op2", "y", "sub", ("var", "y"), ("const", 1),
                 ("if", "y", "power_rec", "power_done"))),
  "power_done": ("print_and_stop", ("var","res"))
}

def resolve(x, env):
    if x[0] ==  "const": return x[1]
    elif x[0] == "var": return env[x[1]]

def interp(block, env):
    while block:
        if block[0] == "op1":
            _, var, op, arg, next = block
            env[var] = do_op(op, env, resolve(arg, env))
        elif block[0] == "op2":
            _, var, op, arg1, arg2, next = block
            a1 = resolve(arg1, env)
            a2 = resolve(arg2, env)
            env[var] = do_op(op, env, a1, a2)
        elif block[0] == "jump":
            next = blocks[block[1]]
        elif block[0] == "print_and_stop":
            next = None
            print resolve(block[1], env)
        elif block[0] == "if":
            _, var, tbranch, fbranch = block
            if env[var]:
                next = blocks[tbranch]
            else:
                next = blocks[fbranch]
        block = next

def do_op(op, env, *arg):
    if op == "same":
        return arg[0]
    elif op == "mul":
        return arg[0] * arg[1]
    elif op == "sub":
        return arg[0] - arg[1]

# run the interpreter
interp(blocks["power"], dict(x=5, y=3))

######################################################################

def plookup(key, env):
    return  ("const", env[key]) if key in env else ("var", key)

def presolve((tag, val), env):
    return ("const", val) if tag == "const" else plookup(val, env)

def pe(block,env):
    if block[0] == "op1":
        _, var, op, arg, next = block
        (tag, val) = presolve(arg, env)
        if tag == "const":
            env[var] = do_op(op, env, val)
            return pe(next, env)
        else:
            del env[var]
            newnext = pe(next, env)
            return ("op1", var, op, (tag, val), newnext)
    elif block[0] == "op2":
        _, var, op, arg1, arg2, next = block
        (tag1, val1) = presolve(arg1, env)
        (tag2, val2) = presolve(arg2, env)
        if tag1 == "const" and tag2 == "const":
            env[var] = do_op(op, env, val1, val2)
            return pe(next, env)
        else:
            if var in env: del env[var]
            newnext = pe(next, env)
            return ("op2", var, op, (tag1, val1), (tag2, val2), newnext)
    elif block[0] == "jump":
        return ("jump", do_pe(block[1], env))
    elif block[0] == "print_and_stop":
        return ("print_and_stop", presolve(block[1],env))
    elif block[0] == "if":
        _, var, tbranch, fbranch = block
        (tag, val) = plookup(var, env)
        if tag == "const":
            b = do_pe(tbranch if val else fbranch, env)
            return ("jump", b)
        else:
            tb = do_pe(tbranch, env)
            fb = do_pe(fbranch, env) 
            return ("if", (tag, val), tb, fb)

code_cache = []

def do_pe(label, env):
    for k, newlabel in code_cache:
        if k == (label, env): 
            return newlabel
    newlabel ="%s_%d" % (label, len(code_cache))
    code_cache.append( ((label,env.copy()), newlabel) )
    blocks[newlabel] = pe(blocks[label], env)
    return newlabel

# generate a new specialized program
pe_label = do_pe("power", dict(y=5))
# run the specialized program
interp(blocks[pe_label], dict(x=5))

Gitosis

Adapted from http://blog.agdunn.net/?p=277

pacman -S git-core setuptools
useradd --home-dir=/media/STORAGE/git --create-home --system git
su -l git

git clone git://eagain.net/gitosis.git
cd ~/gitosis
patch gitosis/ssh.py <<EOF
37c37
<     TEMPLATE=('command="gitosis-serve %(user)s",no-port-forwarding,'
---
>     TEMPLATE=('command=".local/bin/gitosis-serve %(user)s",no-port-forwarding,'
EOF
patch gitosis/templates/admin/hooks/post-update <<EOF
3c3
< gitosis-run-hook post-update
---
> ~/.local/bin/gitosis-run-hook post-update
EOF
git commit -a -m 'Adapt Gitosis for being installed with python setup.py install --user' --author 'Lars Rasmusson <Lars.Rasmusson@gmail.com>'
python2.7 setup.py install --user

~/.local/bin/gitosis-init  
[ paste your public ssh key and press CTRL-D ]

chmod u+x ~/repositories/gitosis-admin.git/hooks/post-update

Now you can clone the repository gitosis-admin.git from the server using

git clone git@servername:gitosis-admin.git

To add a user with pubkey file username.pub

cp username.pub gitosis-admin/keydir/
(cd gitosis-admin; git commit keydir -m 'added user'; git push)

To give the user access to a repository, add him to a group
(or create a new group for him), and add the repository name
to the ‘writable’ list for that group in gitosis-admin/gitosis.conf

Python sudoku

# Lars.Rasmusson@gmail.com 2011-12-18
class sudoku(dict):
    def __init__(self,game):
        game = [g for g in game if g in ".123456789"]
        for r in range(1,10):
            for c in range(1,10):
                self[(r,c)] = set(range(1,10)) if game[0] == '.' \
                              else set([int(game[0])])
                game = game[1:]
    def row(self, r): return [(r,c) for c in range(1,10)]
    def col(self, c): return [(r,c) for r in range(1,10)]
    def field(self, f):
        fs = []
        for x in range(1,10):
            r = (x - 1) // 3 + 3 * ((f - 1) // 3) + 1
            c = (x - 1) % 3 + 3 * ((f - 1) % 3) + 1
            fs.append((r,c))
        return fs
    def different(self, vars, n):
        from itertools import combinations
        modified = False
        for vs in combinations(vars, n):
            u = set().union(*[self[x] for x in vs])
            o = set().union(*[self[x] for x in vars if not x in vs])
            if len(u) == n and o.intersection(u) != set():
                for v in set(vars)-set(vs):
                    if self[v].intersection(u):
                        self[v] -= u
                modified = True
        return modified
    def solve(self):
        n = 1
        while n < 9:
            mod = False
            for i in range(1,10):
                mod |= self.different(self.row(i),n)
                mod |= self.different(self.col(i),n)
                mod |= self.different(self.field(i),n)
            n = 1 if mod else n + 1
    def write(self):
        for r in range(1,10):
            for c in range(1,10):
                v = self[(r,c)]
                print '.' if len(v) > 1 else list(v)[0],
            print
    def backtrack(self):
        from copy import deepcopy
        self.solve()
        choices = [len(self[var]) for var in self]
        if min(choices) < 1: return None
        if max(choices) == 1: return self
        var = [var for var in self if len(self[var]) > 1][0]
        for val in self[var]:
            s = deepcopy(self)
            s[var] = set([val])
            s = s.backtrack()
            if s != None: return s
        return None
    def check(self):
        for i in range(1,10):
            s1 = set().union(*[self[v] for v in self.row(i)])
            s2 = set().union(*[self[v] for v in self.col(i)])
            s3 = set().union(*[self[v] for v in self.field(i)])
            if not s1 == s2 == s3 == set(range(1,10)):
                return False
        return True

games = ["""
798 ... 2..
... 69. .73
.6. 27. 1..

6.. 94. .81
4.5 .61 .2.
9.2 8.. .3.

2.7 ... 4..
1.. 4.3 76.
..6 .19 .5.
"""
,
"""
... .4. ...
..5 ... .46
..7 ... ..5
.5. 3.. 2..
23. ... 97.
7.. 8.. ...
.9. .8. 3..
... .24 ...
12. .3. .8.
"""
,

"""
5.. 17. .39
..7 9.. ...
.1. ... 4..

... 8.2 7..
3.8 ... 6.2
..5 4.6 ...

..2 ... .5.
... ..5 9..
15. .29 ..7
"""
,
"""
.2. ..6 ..3
.7. 95. ...
..8 ... ...

..5 ... ...
... 248 .1.
.6. ..3 ..2

39. ... ...
... 1.. 79.
... ... 1..

"""
,
"""
... 76. .5.
..2 ... .9.
... .5. 7..

..4 ..1 ...
.3. ..8 57.
... 2.. 6..

42. .3. ...
7.. 8.. ...
... ... ..1

"""
,
"""
.6. .4. ...
8.. ... ..9
..7 ... 15.

... ..8 ...
..3 .9. 7.4
... ... .6.

.1. 6.. ..3
9.. 1.. 8..
62. ..5 ...
"""
,
"""
5.1 ..8 ...
... .4. .3.
... ... 15.

.6. 49. ...
... 6.. 9.7
..3 1.. ...

... ... .42
.4. 8.7 ...
.27 ... .6.
"""

,
"""

. . 2 | 4 . . | . 8 9
. 4 . | . . 8 | 2 7 .
. . . | . . 6 | . . 4
------|-------|------
. 7 . | 9 . . | . . .
. . . | . . . | . . .
3 . 8 | 5 . . | . . .
------|-------|------
. 9 7 | 3 . 1 | . 6 5
. 8 . | 7 2 . | . . .
4 . . | . . . | . . 8
""",

"""
. 4 3 | 9 8 . | 2 5 . 
6 . . | 4 2 5 | . . . 
2 . . | . . 1 | . 9 4 
------|--------|------ 
9 . . | . . 4 | . 7 . 
3 . . | 6 . 8 | . . . 
4 1 . | 2 . 9 | . . 3 
------|--------|------ 
8 2 . | 5 . . | . . . 
. . . | . 4 . | . . 5 
5 3 4 | 8 9 . | 7 1 . 
"""
,
"""
1..4....8
...89.5..
.2...5...
..8....37
.9..5..2.
36....1..
...1...7.
..6.48...
9....3..4
"""
,
"""
.6. .4. ...
8.. ... ..9
..7 ... 15.

... ..8 ...
..3 .9. 7.4
... ... .6.

.1. 6.. ..3
9.. 1.. 8..
62. ..5 ...
"""
]

if __name__ == "__main__":
    for game in games:
        s = sudoku(game)
        s.write()
        # s.solve()
        s = s.backtrack()
        if s:
            if s.check():
                s.write()
            else:
                print "FAILED CHECK!"
        else:
            print None
        print

Verisign S/MIME certificate for Mac

I ordered a certificate from verisign
"Digital ID for Secure Email"

I did it via Firefox

I filled in name and credit card info
and clicked accept.

A popup asked which key to use and I chose "Software device"
or something like that. I clicked a couple of times.

Then I got an email from verisign telling me
how to retrieve the certificate.

When I retrieved it, I got a webpage called sophia.exe
which contained some certificate and some HTML.
I stripped out the certificate and tried to import it
into Apples "Keychain Access", but I don't think it worked.

Eventually I went back to the Verisign site and went to
Support, and then to "Digital IDs for Secure Email Support"

Then I clicked on Retrieve to try to get the certificate
again. It said I had to use the same browser as before,
which I did, and this time it said everything went ok.

I went into Preferences, Advanced, Encryption, View Certificates,
clicked on my certificate and made a "backup" of it.
That created a pkcs12 file (.p12) which I was able to
import into Keychain Access.

Set ipv6 default route

I have a box that sends out radvd announcements on a lan, but something on the lan makes the other machines forget the advertisement about the default gateway after a while. They remember their ipv6 address, but cannot connect outside the lan anymore.

Before I used to log in to the machine with radvd and restart it so that it sends out fresh advertisements, but I'm now trying to explicitly add the default route with

read -p host: m;
ssh -t ${m:?} sudo ip -6 route add default via fe80::2b0:d0ff:febe:5fd7 dev eth0

Let's see how that goes...

Building bochs

The required libraries must be installed somewhere,
I let MacPorts build and install bochs to get
the libraries installed into /opt/local

Download bochs from svn in SRC, configure and make:

cd $SRC

CFLAGS="-I/opt/local/include -arch i386" \
CXXFLAGS="-L/opt/local/lib -arch i386" \
LDFLAGS="-L/opt/local/lib -arch i386" \
./configure \
--exec-prefix=/opt/local \
--bindir=/opt/local/bin \
--mandir=/opt/local/share/man \
--enable-all-optimizations \
--enable-cdrom \
--with-vbe \
--without-x \
--with-sdl

make -j8

Make a HD image

./bximage -q -hd -mode=sparse -size=1024 $SRC/c.img

./bochs

Configure hard disks, cdrom, bios files and boot order to boot from cdrom.
Use these files

$SRC/c.img
~/Downloads/ubuntu-10.04.2-server-i386.iso

$SRC/bios/BIOS-bochs-latest
$SRC/bios/VGABIOS-lgpl-latest


To make it faster, change the default ips from 50000000 to 4000000
cpu: count=1, ips=4000000, ....

Using a pure python disassembler for x86_64 machine code

Get some machine code, for instance with otool -t /bin/ls | head

$ otool -t /bin/ls | head
/bin/ls:
(__TEXT,__text) section
0000000100001478 6a 00 48 89 e5 48 83 e4 f0 48 8b 7d 08 48 8d 75 
0000000100001488 10 89 fa 83 c2 01 c1 e2 03 48 01 f2 48 89 d1 eb 
0000000100001498 04 48 83 c1 08 48 83 39 00 75 f6 48 83 c1 08 e8 
00000001000014a8 58 0f 00 00 89 c7 e8 1b 39 00 00 f4 55 48 89 e5 
00000001000014b8 48 8d 47 68 48 8d 7e 68 48 89 c6 c9 e9 01 3a 00 
00000001000014c8 00 55 48 89 e5 48 83 c6 68 48 83 c7 68 c9 e9 ef 
00000001000014d8 39 00 00 55 48 89 e5 53 48 89 f1 48 8b 56 60 48 
00000001000014e8 8b 47 60 48 8b 58 30 48 39 5a 30 7f 1d 7c 22 48

Get pymsasid from http://code.google.com/p/pymsasid/

$ wget http://pymsasid.googlecode.com/files/pymsasid-0.31.zip
$ unzip pymsasid-0.31.zip
$ cd pymsasid-0.3

Run it

$ python

import pymsasid
code = "6a 00 48 89 e5 48 83 e4 f0 48 8b 7d 08 48 8d 75 10"
p=pymsasid.Pymsasid(source=code,hook=pymsasid.HexstringHook,vendor=pymsasid.VENDOR_AMD)
p.dis_mode = 64
p.pc = 0x0000000100001478
for i in range(5): print p.decode()

will print

push 0x0 
mov rbp rsp 
and rsp 0xf0 
mov rdi [rbp+0x8] 
lea rsi [rbp+0x10]