Xmonad and uzbl-browser

Dienstag, 6. September 2011

Every release of Opera seems to add more bugs¹ and useless features², whereas Firefox is featureless and slow without or feature-rich and ineffable slow with Add-ons. Time for an alternative! What I want is a small browser with external configurable handlers. What I don't need is qt-bloat, a Firefox clone or something with lua in it. uzbl seems to fit, but I'm tired of learning new shortcuts for tabbing implementations. Everyone and his brother integrate tabs (terminal multiplexer, terminal, browser, editor...) but only one application should obviously manage tabs - the window manager. It turned out that my original configuration of xmonad wasn't the optimal solution. I'd like to have the following behaviour:

First workspace: keep master, switch focus to new window

+---------------+ +-----------+---+
| | | | 2 |
| | | | |
| 1 | -> | 1 | f |
| (focus) | | | o |
| | | | c |
| | | | . |
+---------------+ +-----------+---+


Second to fourth workspace: switch master and focus

+---------------+ +-----------+---+
| | | | 1 |
| | | | |
| 1 | -> | 2 | |
| (focus) | | (focus) | |
| | | | |
| | | | |
+---------------+ +-----------+---+


Fifth workspace (for browsing): keep master and focus and use tabbed layout (open new links/tabs in background)

+---------------+ +-------+-------+
+---------------+ +-------+-------+
| | | |
| 1 | -> | 1 |
| (focus) | | (focus) |
| | | |
| | | |
+---------------+ +---------------+


These are the steps that were necessary to achieve this:

1. copy xmonad-contrib-0.9.2/XMonad/Hooks/InsertPosition.hs to ./xmonad/lib/
2. apply the patch (sorry, no google account and no desire to install darcs again):

--- InsertPosition.hs
+++ InsertPositionNew.hs
@@ -16,15 +16,16 @@
 module XMonad.Hooks.InsertPosition (
     -- * Usage
     -- $usage
-    insertPosition
+    insertPosition,
+    insertPositionPerWorkspace
     ,Focus(..), Position(..)
     ) where

-import XMonad(ManageHook, MonadReader(ask))
+import XMonad(ManageHook, MonadReader(ask), WorkspaceId)
 import qualified XMonad.StackSet as W
 import Control.Applicative((<$>))
 import Data.Maybe(fromMaybe)
-import Data.List(find)
+import Data.List(find,lookup)
 import Data.Monoid(Endo(Endo))

 -- $usage
@@ -44,26 +45,30 @@
 -- | insertPosition. A manage hook for placing new windows. XMonad's default is
 -- the same as using: @insertPosition Above Newer@.
 insertPosition :: Position -> Focus -> ManageHook
-insertPosition pos foc = Endo . g <$> ask
+insertPosition = insertPositionPerWorkspace []
+
+-- | Specify an insertPosition for a particular Workspace.
+insertPositionPerWorkspace :: [(WorkspaceId, (Position, Focus))] -> Position -> Focus -> ManageHook
+insertPositionPerWorkspace l pos foc = Endo . g <$> ask
   where
-    g w = viewingWs w (updateFocus w . ins w . W.delete w)
-    ins w = (\f ws -> fromMaybe id (W.focusWindow <$> W.peek ws) $ f ws) $
-        case pos of
+    g w = viewingWs w (\i -> updateFocus i w . ins i w . W.delete w)
+    ins i w = (\f ws -> fromMaybe id (W.focusWindow <$> W.peek ws) $ f ws) $
+        case fst $ fromMaybe (pos,foc) (lookup i l) of
             Master -> W.insertUp w . W.focusMaster
             End    -> insertDown w . W.modify' focusLast'
             Above  -> W.insertUp w
             Below  -> insertDown w
-    updateFocus =
-        case foc of
+    updateFocus i =
+        case snd $ fromMaybe (pos,foc) (lookup i l) of
             Older -> const id
             Newer -> W.focusWindow

 -- | Modify the StackSet when the workspace containing w is focused
-viewingWs :: (Eq a, Eq s, Eq i, Show i) =>a-> (W.StackSet i l a s sd -> W.StackSet i l a s sd)-> W.StackSet i l a s sd-> W.StackSet i l a s sd
+viewingWs :: (Eq a, Eq s, Eq i, Show i) =>a-> (i -> W.StackSet i l a s sd -> W.StackSet i l a s sd)-> W.StackSet i l a s sd-> W.StackSet i l a s sd
 viewingWs w f = do
     i <- W.tag . W.workspace . W.current
     ws <- find (elem w . W.integrate' . W.stack) . W.workspaces
-    maybe id (fmap (W.view i . f) . W.view . W.tag) ws
+    maybe id (fmap (W.view i . f i) . W.view . W.tag) ws

 -- | 'insertDown' and 'focusLast' belong in XMonad.StackSet?
 insertDown :: (Eq a) => a -> W.StackSet i l a s sd -> W.StackSet i l a s sd
 

3. reconfigure ./xmonad/xmonad.hs

add imports:

import InsertPositionNew
import XMonad.Hooks.ManageHelpers
import XMonad.Layout.PerWorkspace
 


add shortcut for uzbl-browser:

    , ((modm,               xK_u), spawn "uzbl-browser")
 


change layout hook:

myLayout =
  modWorkspaces myWorkspaces avoidStruts $
  onWorkspace "5:www" simpleTabbedAlways $
  tiled ||| Mirror tiled ||| simpleTabbedAlways ||| Full
  where
     -- default tiling algorithm partitions the screen into two panes
     tiled   = Tall nmaster delta ratio

     -- The default number of windows in the master pane
     nmaster = 1

     -- Default proportion of screen occupied by master pane
     -- ratio   = 1/2
     ratio   = 7/10

     -- Percent of screen to increment by when resizing panes
     -- delta   = 3/100
     delta   = 5/100
 


create manage hooks

myManageHookFloat = composeAll
    [ className =? "Gimp"           --> doFloat
    , className =? "MPlayer"        --> doFloat
    ,(className =? "Firefox" <&&> role =? "Manager" ) --> doFloat
    ] <+> composeOne [
      isDialog -?> doCenterFloat
    ]
    where role = stringProperty "WM_WINDOW_ROLE"

myManageHookShift = composeAll
    [ className =? "Uzbl-core"      --> doShift "5:www"
    , className =? "Firefox"        --> doShift "5:www" ]

myManageHookPosition = insertPositionPerWorkspace [("1",(Below,Newer)),("5:www",(Below,Older))] Above Newer
 


combine manage hooks and override the default config:

        manageHook         = myManageHookFloat <+> myManageHookPosition <+> myManageHookShift,
 


Done.

multiple uzbl-browser windows within xmonad tabbed layout

¹ last one: the bookmark menu needs 30s to load all bookmarks
² webserver(!), torrent- and unusable mail client

Verweisaktualisierung

Samstag, 3. September 2011

Auswahl


-userfriendly.org

Bücher


-The Art of Assembly Language Programming
+The Art of Assembly Language Programming

Software


-BackTrack
-Linux From Scratch
-TUD:OS
-IPython
-Kodos
-Languages for the Java VM (E,Glossary)
-PHP :|
-Processing (Complexification)
-Scala (Simply Scala)
-Ettercap
-Firefox
-Madwifi
-Opera (Bug Report, Desktop-Team)
-vsftpd
-Web Scraping Proxy
-Wireshark
+uzbl
-bootchart
-chrootkit
-gentoo:dep
-John the Ripper
-mrxvt
-Mupad
-Mysql
-Nmap
-rootkit hunter
-scanlogd
-vim (colour schemes, why, Cookbook)
-Visitors
-xxdiff
-Yafc
-Weblog
-Dia
-dwm
-GQview
-gv
-mpg123
-TCM
-xchm
-xine
-Big Boards
-Chaosseminar: Personal Firewalls
-Efficient String Concatenation in Python
-felinemenace
-Heiner's SHELLdorado
-Java Decompiler
-milw0rm
-Online Java Decompiler
-p nand q
-packet storm
-ReportLab Toolkit
-rootkit.com
-SearchIRC
-SecuriTeam
-SecurityTube
-shellcode
-Technical info
-Warum Disclaimer dem WWW schaden

Sonstiges


-DUDEN - Besserwisserspiel
-Andrew Kennedy
-BILDblog
-Christian
+Edward Z. Yang
-Ilja
-Matthew Podwysocki
-Peteris Krumins
-vs-geheim

ne keycodes

Mittwoch, 24. August 2011

To get expected behaviour for home, end and backspace in ne with rxvt-unicode, start ne (the "nice editor"), press Ctrl+k for the command prompt, enter kc and in the new prompt press the specific key for the key code. Afterwards adjust the config file:
>cat .ne/.keys
KEY 105 MoveSOL
KEY 106 MoveEOL
KEY  7f Backspace

Ich war der Fahrer von Rommel

Dienstag, 23. August 2011

Ich war der Fahrer von Rommel
Vor 70 Jahren marschierte die Wehrmacht unter Erwin Rommel in Nordafrika ein. Rudolf Schneider aus Stauchitz war dessen Frontfahrer.
Schneider ist Träger des Eisernen Kreuzes 1. Klasse – die dritthöchste Auszeichnung für Wehrmachtssoldaten.

Gleich nach Deutschem Kreuz und Ritterkreuz oder wie? m(
UNO bekräftigt das Recht auf Gotteslästerung

Die Stellungnahme kam vom Menschenrechtskomitee, dem Gremium aus achtzehn unabhängigen Experten, die damit beauftragt wurden, Beschwerden hinsichtlich des Internationalen Pakts über Bürgerliche und Politische Rechte (ICCPR, International Covenant on Civil and Political Rights), das Menschenrechtsabkommen von 1966, das für Meinungsfreiheit und Ausdrucksfreiheit sorgt, sowie für andere fundamentale Rechte zu bewerten. [...] Anders als die weit veröffentlichten Resolutionen, die vom Menschenrechtsrat und der Generalversammlung produziert werden, sind die Vorschriften des ICCPR für seine über 165 Mitglieder juristisch bindend.

Laut Paragraph 48 „sind Verbote von Darstellungen mangelnden Respekts vor einer Religion oder anderen Glaubenssystemen, einschließlich Blasphemiegesetzen, mit dem Vertrag inkompatibel, außer in den bestimmten Umständen, wie sie in Artikel 20, Absatz 2 des Vertrags vorausgesehen sind.“ Der Artikel 20, Absatz 2 ruft Staaten dazu auf, Folgendes zu verbieten: „Die Verfechtung nationalen, rassistischen oder religiösen Hasses, welche zur Diskriminierung, Feindseligkeit oder Gewalt anstiftet.“ Der Kommentar verlangt mit Bedacht, dass keine Restriktion die Garantien des Abkommens auf Gleichberechtigung vor dem Gesetz (Artikel 26) und der Freiheit des Denkens, des Gewissens und der Religion (Artikel 18) verletzen darf.

Da haben die Sekten wohl vergessen einige Posten zu unterwandern.

General Comment No. 34

Religionsdebatte in der SPD

Sonntag, 14. August 2011

Trennung von Staat und Kirche? Um Gottes Willen!

Die Domain www.spd-laizisten.de wurde ihnen von der Parteiführung untersagt, jetzt sind sie unter www.laizistische-sozis.de zu erreichen. Ganz schön viel Repression gegen einen Verband, dem mit Ingrid Matthäus-Maier, Rolf Schwanitz und Doris Barnett auch einige prominentere Sozialdemokraten angehören. Die SPD will die Laizisten jedenfalls nicht einmal als offiziellen Arbeitskreis anerkennen.

Die Insiderberichte von Mobbing und vom Abschneiden vom Informationsfluss, sobald man sich als Laizist zu erkennen gibt, scheinen also zu stimmen.

Sehr zur Freude von Wolfgang Thierse, dem Sprecher des Arbeitskreises "Christen in der SPD". Der hatte schon zuvor die Befürchtung geäußert, seine Partei werde durch die 500 eingetragenen Laizisten "thematisch eingeengt." Was Lösch zu der Frage bringt, "wo denn die Einengung ist, wenn es uns nicht geben darf, aber einen Arbeitskreis Christen?"

Gerade Thierse, der mit seinem mangelnden Demokratieverständnis hier in Dresden alljährlich im Februar auffällt. Ein Toleranzverständnis, wie es in den Kirchen gepredigt wird und das an der eigenen Pforte aufhört.

Auch die Bundestagsabgeordnete Kerstin Griese habe sich gegen den Verband ausgesprochen mit der Behauptung, der Laizismus widerspreche Teilen des SPD-Programms.

Die SPD ist eh unwählbar, ob die jetzt auch noch die Kirche als Parteiführung haben, spielt keine Rolle mehr.

checking string routines with Klee

Dienstag, 9. August 2011

Two months ago I discovered some bugs in libpng (CVE-2011-2501, CVE-2011-2692). In the discussion¹ of the second bug I have criticized that libpng is often too permissive in the chunk validation. An example was the unchecked use of strtod(), which allows "infinity" or "nan" as valid values in the ASCII floating point representation in sCAL or pCAL chunks.

These chunks contain byte strings in a quite simple format:

1.2. Floating-point values



The core of PNG does not use floating-point numbers anywhere; it uses integers or, where applicable, fixed-point fractional values. However, special-purpose chunks may need to represent values that do not fit comfortably in fixed-point notation. The textual floating-point notation defined here is recommended for use in all such cases. This representation is simple, has no a priori limits on range or precision, and is portable across all machines.

A floating-point value in this notation is represented by an ASCII text string in a standardized decimal floating-point format. The string is variable-length and must be terminated by a null (zero) character unless it is the last item in its chunk. The string consists of an optional sign ("+" or "-"), an integer part, a fraction part beginning with a decimal point ("."), and an exponent part beginning with an "E" or "e" and optional sign. The integer, fraction, and exponent parts each contain one or more digits (ASCII "0" to "9"). Either the integer part or the fraction part, but not both, may be omitted. A decimal point is allowed, but not required, if there is no fraction part. The exponent part may be omitted. No spaces or any other character besides those specified may appear.

Note in particular that C-language "F" and "L" suffixes are not allowed, the string "." is not allowed as a shorthand for 0 as in some other programming languages, and no commas or underscores are allowed. This format ought to be easily readable in all programming environments.


Later I wondered, if I can use KLEE to find specification mismatches in string handling routines. And what should I say, it worked. I just tested in one direction: if strtod() returns without an error, the string should be valid according to the PNG specification. Of course that's wrong, but this assumption should reveal the cases where the strtod() implementation and the PNG specification differ.


#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#include <klee/klee.h>

int is_png_fp(char* p, char* pe) {
        int cs;

        %%{
                machine png_fp;
                write data;

                main := [+\-]? (([0-9]+ '.'?) | ([0-9]+ '.' [0-9]+) | ('.' [0-9]+)) ([Ee][+\-]? [0-9]+)?;
                write init;
                write exec;
        }%%

        return cs >= png_fp_first_final;
}

int main(int argc, char **argv) {
        double d;

        // create symbolic string
        char *s  = "____";
        klee_make_symbolic(s,5,"s");
        s[4] = '\0';
        char *se = s + strlen(s);
        char *se_= se;

        // call strtod and omit error cases
        errno = 0;
        d = strtod(s,&se_);
        if ((errno != 0) || (s == se_)) {
                klee_silent_exit(1);
        }

        // ---- mismatches ----
        // data: '0z\x00\x00\x00' (allowed trailing characters)
        if (*se_ != '\0') { klee_silent_exit(2); }
        // data: '\x0c0\x00\x00\x00' (allowed leading whitespace)
        if (isspace(s[0])) { klee_silent_exit(3); }
        // data: 'iNF\x00\x00' (infinity)
        if (isinf(d)) { klee_silent_exit(4); }
        // data: 'nAN\x00\x00' (not a number)
        if (isnan(d)) { klee_silent_exit(5); }

        // assertion: s is in png ascii floating point format
        assert(is_png_fp(s,se));

        return 0;
}


For the description of the floating point strings I used a regular expression. In is_png_fp() this regular expression is converted into an automaton via ragel to forgo unnecessary regex-libraries. If one runs the example code with KLEE, the cases in the "mismatches"-section break the assertion. Leading whitespaces, trailing characters, infinity and not a number - all valid in C99/POSIX/GNU but not in PNG. At first I missed the hexadecimal representation but then I realized, that the uclibc I use with KLEE was build without hex-support.

A quick sample run with commented mismatch section in example.c for those who want to follow my short notes. ;)

>ragel -m -o gen.c example.c
>llvm-gcc -c -emit-llvm -I<path to klee>/include gen.c -o genc
>klee --libc=uclibc --optimize --only-output-states-covering-new ./genc
KLEE: output directory = "klee-out-37"
WARNING: While resolving call to function '__user_main' arguments were dropped!
KLEE: WARNING: undefined reference to function: _stdio_term
KLEE: WARNING: undefined reference to function: fcntl
KLEE: WARNING: undefined reference to function: fstat
KLEE: WARNING: undefined reference to function: open
KLEE: WARNING: executable has module level assembly (ignoring)
KLEE: WARNING: silently concretizing (reason: floating point) expression (Add w32 4294967248
         (SExt w32 (Read w8 0 arr1))) to value 7 (:0)
KLEE: ERROR: ASSERTION FAIL: is_png_fp(s,se)
KLEE: NOTE: now ignoring this error at this location

KLEE: done: total instructions = 154995
KLEE: done: completed paths = 645
KLEE: done: generated tests = 13


The first found case are the trailing characters:

>ktest-tool klee-last/test000002.ktest
ktest file : 'klee-last/test000002.ktest'
args       : ['./genc']
num objects: 1
object    0: name: 's'
object    0: size: 5
object    0: data: '777z\x00'


A satisfying regular expression is:

                dec    = [+\-]? (([0-9]+ '.'?) | ([0-9]+ '.' [0-9]+) | ('.' [0-9]+)) ([Ee][+\-]? [0-9]+)?;
                main  := space* (/inf/i | /nan/i | dec) any*;

Keep in mind, that this is no equivalence check. The defined language could be a superset of the language of the accepted strings of strtod().

The corresponding automata images were generated with dot:
>ragel -mpV example.c | dot -Tgif -o ragel_strtod.gif


strtod():
strtod automaton

png floating point:
png floating point automaton

Papers you might be interested in:


¹ No, I still don't know their definition of "non-positive".

33. Kirchentag

Sonntag, 5. Juni 2011

Frauenkirche überfüllt

Endlich überstanden. Bei all den Opfern klerikaler Gehirnwäsche konnte man gar nicht so schnell zwischen Mitleid und Fremdschämen wechseln, wie es angebracht war. In jeder Straße, auf jedem Platz, in jedem Saal nur grüne Schals und violette Werbung. Der Gang durch die Innenstadt wurde zur Tortur: langweilige Predigten, schlechte Musikanten und dazwischen evangelikale Menschenfänger und debil grinsende Handzettelverteiler. Besonders deprimierend war es, wieder einmal vor Augen gehalten zu bekommen, wie unterwandert die Gesellschaft von diesem Menschheitsvirus ist. Sämtliche Parteien gaben sich ein Stelldichein, die Uni machte mit, das Rathaus flaggte, hohe Medienvertreter kamen und auch unsere politische Führung folgte dem Ruf der Sekten: Günter Beckstein, Joachim Gauck, Katrin Göring-Eckardt, Reinhard Höppner, Hannelore Kraft, Renate Künast, Hans Leyendecker, Thomas de Maizière, Angela Merkel, Andrea Nahles, Claudia Roth, Norbert Röttgen, Annette Schavan, Frank-Walter Steinmeier, Stanislaw Tillich, Christian Wulff usw. usf.

Rathaus

Man machte auch keinen Hehl daraus:

sz

und kam mit gefälligen Themen, wie dem Atomausstieg, ein bisschen Umwelt- und Friedenspolitik und dem bösen Rechtsextremismus. Captain Obvious kam viel zu oft zu Wort.

Die konfessionslosen Dresdner (80%) machten einen großen Bogen um die Innenstadt und ärgern sich über die 7,9Mio. Euro Steuergelder, die für diese unnütze Vereinsfeier aus dem Fenster geworfen wurden.

Baden im Ganges:
Baden im Ganges

Jesus mit Fahrrad:
Jesus mit Fahrrad

Martin Luther höchstpersönlich:
Martin Luther

Ökopolitik:
Ökopolitik

Werner "Glauben Sie, dass Ihr Opa ein Affe war?" Nachtigal:
Wanderprediger

Wir befinden uns im Jahre 2011 n. Chr. Ganz Dresden ist von Sektierern besetzt. Ganz Dresden? Nein! Eine von unbeugsamen Humanisten bevölkerte Burg hört nicht auf, dem Eindringling Widerstand zu leisten.

Zum Glück gab es die Veranstaltungen des GeFAHR eV. um den violetten Stumpfsinn zumindest kurzzeitig zu vergessen. Es kamen ua. Carsten Frerk, Heinz-Werner Kubitza und Michael Schmidt-Salomon.

Vorträge GeFAHR eV.

Zitate:
"Durch zwei Diktaturen hat die Weitergabe des Glaubens im Osten einen Bruch erlebt", analysiert Dietrich Bauer, Dezernent für Gemeindeaufbau in der Evangelisch-lutherischen Landeskirche Sachsens. "Die Menschen sagen, sie seien ohne christlichen Glauben glücklich und könnten Probleme lösen."

Genauso erklärt auch Albrecht Steinäuser die große Schere zwischen Werten und Glauben: "Viele Menschen verbinden nichts mehr mit christlichem Glauben und führen die Werte nicht unbedingt auf das Christentum zurück."

(evangelisch.de)

Derzeit hat die [Giordano-Bruno-]Stiftung mehr als 2.500 Fördermitglieder. Das ist auf den ersten Blick nicht viel. Was hier zählt, ist jedoch weniger die Zahl der Unterstützer als vielmehr deren politischer Einfluss. So hat vor einiger Zeit Ingrid Matthäus-Maier, viele Jahre stellvertretende Vorsitzende der SPD-Bundestagsfraktion, ihre Mitarbeit erklärt. Über sie laufen die Bemühungen, einen sogenannten "Laizistischen Arbeitskreis in der SPD" zu gründen. Vorerst hat der SPD-Parteivorstand dieses Ansinnen abgelehnt. Aber was nicht ist, kann Dank reger Kontaktpflege ja noch werden.

(evangelisch.de)

resort PNG chunks

Dienstag, 5. April 2011

If you ever needed to resort or drop chunks in a png file or to repair the signature and crc values, this one-evening-hack might be useful next time.

Resort chunks:

>./png_resort.py brokensuite/hist_after_idat.png foo.png
File: brokensuite/hist_after_idat.png
No. Type (Position,Length)
--------------------------
 0. IHDR (8,25)
 1. gAMA (33,16)
 2. sBIT (49,15)
 3. PLTE (64,57)
 4. IDAT (121,83)
 5. hIST (204,42)
 6. IEND (246,12)
Enter new order (p.ex.: 0,3..5,2): 0..3,5,4,6
New order: [0, 1, 2, 3, 5, 4, 6]
 


Drop chunks and repair crc:

>./png_resort.py brokensuite/chunk_crc.png bar.png
File: brokensuite/chunk_crc.png
No. Type (Position,Length)
--------------------------
[Error] Test failed: chunk crc
repair crc [y|n]:y
 0. IHDR (8,25)
 1. gAMA (33,16)
 2. PLTE (49,780)
 3. IDAT (829,445)
 4. IEND (1274,12)
Enter new order (p.ex.: 0,3..5,2): 0,2..4
New order: [0, 2, 3, 4]
 


For huge chunks you have to implement a more intelligent buffering (see read_bytes and writing).


#!/usr/bin/python3

# select chunks from infile.png and write them resorted to outfile.png

# usage: png_resort.py <infile.png> <outfile.png>
# user input:
#   comma separated list of chunk indices or index ranges
#     p.ex.: 0,2..4,1,5
#   or 'exit'

# Literature
# ----------
# Portable Network Graphics (PNG) Specification (Second Edition)

import readline,struct,sys,zlib # drop readline for less dependencies and comfort
from functools import *
from io import *



png_signature = b'\x89\x50\x4e\x47\x0d\x0a\x1a\x0a'


def print_error(*msgs):
        """print highlighted error message(s)"""

        msgs = ' '.join(map(str,msgs))
        print('\033[1;31m[Error] {0}\033[1;m'.format(msgs))


def test(title,condition,val=None):
        """test condition, if false print test title and (maybe) val"""

        if condition: return True
        else:
                s = 'Test failed: {0} ({1})'.format(title,s) if val else 'Test failed: {0}'.format(title)
                print_error(s)
                return False


def check_png_signature(f):
        """read and validate png file signature"""

        # file signature (5.2)
        sig = f.read(8)

        return \
                test('signature length',len(sig) == 8) and \
                test('signature',sig == png_signature)


def is_png_uint32(val):
        # (7.1)
        return 0 <= val < 2**31


def png_chunks(f):
        """file -> [{'type','pos','length'[,'crc']}]"""

        # chunk layout (5.3)
        # +-------------------------------------------------+
        # | length (4) | type (4) | data (length) | crc (4) |
        # +-------------------------------------------------+

        def read_bytes(name,length):
                """read length bytes"""
                val = f.read(length)

                if len(val) < length:
                        print_error('{0} < {1}'.format(name,length))
                        raise ValueError
                else: return val


        ret = []
        cnt = 0

        print('No. Type (Position,Length)\n'+'-'*26)
        while True:
                # read chunk
                pos = f.tell()
                length_ = f.read(4)
                if len(length_) == 4:
                        (length,) = struct.unpack_from('!I',length_,0)
                        try:
                                type_ = read_bytes('chunk type',4)
                                data  = read_bytes('chunk data',length) if length > 0 else b''
                                crc__ = read_bytes('chunk crc',4)
                        except:
                                print_error('defective chunk')
                                break
                        else:
                                type = ''
                                try:
                                        type = type_.decode('ascii')
                                except:
                                        print_error('non-ascii characters in type')
                                        type = type_.decode('ascii','replace')

                                (crc_,) = struct.unpack_from('!I',crc__,0)
                                zcrc = zlib.crc32(type_+data)
                                crc = crc_ == zcrc

                                chunk_attrs = {'type':type,'pos':pos,'length':length+12}

                                # (5.1)
                                test('chunk length limit',is_png_uint32(length),length)
                                # check crc and repair
                                if not test('chunk crc',crc,crc):
                                        while True:
                                                c = input('repair crc [y|n]:').strip().lower()
                                                if c == 'y':
                                                        chunk_attrs['crc'] = struct.pack('!I',zcrc)
                                                        break
                                                elif c == 'n': break
                                                else: print_error("wrong input, just y or n")

                                ret.append(chunk_attrs)
                                print('{3:>2}. {0} ({1},{2})'.format(type,pos,length+12,cnt))
                                cnt += 1
                # eof
                elif len(length_) == 0: break
                # error
                else:
                        print_error('defective chunk length')
                        break

        return ret


def order_from_string(s):
        """create list of numbers from string s"""

        err = False

        def convert(si):
                nonlocal err

                if si == '': return []

                try:
                        # simple integer conversion
                        i = int(si)
                except:
                        # range notation
                        try:
                                a,b = si.split('..')
                                c,d = int(a),int(b)
                                l   = []
                                if c < d:
                                        l = list(range(c,d+1))
                                else:
                                        l = list(range(d,c+1))
                                        l.reverse()
                        except:
                                print_error('unknown representation:',si)
                                err = True
                                return []
                        else: return l
                else: return [i]


        order = reduce(lambda x,i:x+convert(i),s.strip().split(','),[])

        return order if not err else None



if __name__ == '__main__':
        # command line arguments
        if len(sys.argv) != 3:
                print_error('Incorrect number of arguments.\n' \
                        'usage: png_resort.py <infile.png> <outfile.png>')
                exit(1)

        try:
                # read file
                infile_name = sys.argv[1]
                print('\033[1;32mFile: {0}\033[1;m'.format(infile_name))
                with open(infile_name,'rb') as infile:
                        # read signature
                        check_png_signature(infile)

                        # read chunks
                        chunks = png_chunks(infile)
                        if len(chunks) == 0: exit(0)

                        # ask for new order
                        while True:
                                cmd = input('Enter new order (p.ex.: 0,3..5,2): ')
                                cmd = cmd.strip()
                                if cmd == 'exit': exit(0)

                                order = order_from_string(cmd)
                                if order == None: continue
                                print('New order: {0}'.format(order))

                                # check new order
                                if not reduce(lambda b,v: b and 0 <= v < len(chunks),order,True):
                                        print_error('unknown chunk indices in new order')
                                else: break

                        # write new file
                        outfile_name = sys.argv[2]
                        with open(outfile_name,'wb') as outfile:
                                # write signature
                                outfile.write(png_signature)

                                # write chunks
                                for chunk_no in order:
                                        c = chunks[chunk_no]
                                        infile.seek(c['pos'],SEEK_SET)
                                        # !!! needs advanced buffering for big files
                                        data = infile.read(c['length'])
                                        data = data if 'crc' not in c else data[:-4]+c['crc']
                                        written = outfile.write(data)
                                        if not c['length'] == len(data) == written:
                                                print_error('copy error')
                                                exit(1)

        except IOError as err:
                print_error(err)
                exit(1)

        exit(0)
 

Sektenverweise

Montag, 7. März 2011

Die Zeit ist knapp, die Verweisliste voll, daher gesammelt in einem Beitrag:

Sekten und Politik:
Ursula von der Leyen und die religiösen Fanatiker
Die religiöse Rechte scheint eine besondere Anziehungskraft auf Politiker auszuüben, die offensiv mit ihrem christlichen Glauben umgehen und versuchen, diesen in Politik, vor allem aber in Wählerstimmen umzusetzen. Ein gelegentlicher Auftritt am "äußerst rechten Rand" des Christentums kann die bibeltreuen Christen bei der nächsten Wahl gewogen stimmen, die restliche Bevölkerung wird diesen Ausflug zu den Fundamentalisten nicht bemerken, so scheint das Kalkül. So fand sich beispielsweise Christian Wulff im Kuratorium von ProChrist wieder [...], einem Missionierungsverein, der Experten wie der Journalistin und Theologin Kirsten Dietrich als fundamentalistisch gilt.

Neben Wulff mit von der Partie: Annette Schavan, Franz Josef Jung, Volker Kauder und Ursula von der Leyen.

Staat stützt Kirchen mit Milliarden
Das Buch dürfte die Debatte um die künftige Finanzierung der Kirchen anheizen. Nach Frerk betragen die direkten und indirekten Leistungen, die der Staat Katholiken und Protestanten und deren Einrichtungen bisher gewährt, jährlich insgesamt rund 19 Milliarden Euro. Diese Summe enthält nicht die neun Milliarden Euro Kirchensteuern und die schätzungsweise 45 Milliarden für Caritas und Diakonie.


Sekten und Geldwäsche:
Glasnost bei der Vatikanbank?
Die Vatikanbank darf von der Polizei nicht durchsucht, ihre Telefone nicht abgehört und ihre Mitarbeiter nicht verhört werden. Für sie galten bis vor kurzer Zeit weder die Kontrollbestimmungen im Bankenverkehr noch die internationalen Regeln zum Schutz vor Geldwäschepraktiken. Ihre Bilanzen unterliegen striktester Geheimhaltung. Um Informationen über die Geschäfte dieser Bank zu erlangen, muss ein Staatsanwalt ein Rechtshilfeersuchen stellen, das in der Regel nicht gewährt wird. Ihre leitenden Mitarbeiter genießen weitgehend Immunität. Außerdem sind ihre Kapitalerträge von der Steuer befreit.


Sekten und Missbrauch:
Belgian child abuse report exposes Catholic clergy
Paedophilia expert unveils harrowing testimony and documents cases in almost every diocese


Missbrauchsopfern droht der Maulkorb
Drei Bundesministerinnen, 60 Experten: Am Runden Tisch zum Missbrauch stehen die Interessen von Institutionen und Parteien im Zentrum, nicht die der Opfer. Jetzt geht es um mögliche Entschädigungen. Etliche Betroffene haben ganz andere Probleme: Sie sehen sich Klagen mutmaßlicher Täter ausgesetzt.


"Auffälligkeiten" und Vertuschungen
159 "auffällige" Priester, hohe Dunkelziffer, systematische Vertuschung: Das ist das Ergebnis einer Untersuchung des Bistums München und Freising zu den Missbrauchsfällen der Vergangenheit. Die Gutachterin bemängelte ein "klerikales Selbstverständnis", Skandale zu vermeiden.

Die böse NVA

Montag, 7. März 2011

Empörung über NVA-Feier im Tierpark
100 Veteranen der DDR-Truppe marschierten am Samstag in Uniform zum Armeejubiläum im Tierpark auf. Landespolitiker distanzieren sich von dem DDR-Gedenkfest, die SPD fordert Konsequenzen.

Wieder ein schöner Grund sich aufzuplustern. Ob sich Traditionsverbände der Wehrmacht, Hiag-Ableger, OdR usw. treffen ist vollkommen egal (mir auch), aber bei der NVA ist Schluss! Böse, böse Armee - die hat ja nicht einmal Krieg geführt!1elf

Die üblichen Beteiligten mit Blockwartsyndrom:
Die Leitung von Zoo und Tierpark verurteilten das Treffen gestern scharf. [...] Der Cafeteria-Betreiber wie auch ein Tierpark-Mitarbeiter, der von dem Treffen gewusst, die Geschäftsführung aber nicht informiert habe, erhalten eine Abmahnung, kündigte sie an.

[...] der Verfassungsschutzexperte der SPD, Tom Schreiber. Der Tierpark erhalte Landesgelder. „Die Verantwortlichen müssen ein klares Signal setzen und den Cafeteria-Pächter abmahnen.“


Dass Text und Zitat nicht zusammen passen ignorieren wir mal:
Auch die Linkspartei distanzierte sich am Sonntag am Rande ihrer Klausurtagung entschieden von den NVA-Veteranen. „Diese Gruppierung hat keinerlei politische Relevanz in unserer Partei“, sagte Landeschef Klaus Lederer.


„Es kann doch nicht sein, dass der Tierpark seine Tore für Systemträger einer Diktatur öffnet“, sagte der Vize-Bundesvorsitzende der Vereinigung der Verfolgten des Stalinismus (VOS), Ronald Lässig. Zugleich forderte er, Uniformen und Symbole der DDR müssten in der Öffentlichkeit ebenso verboten sein wie nationalsozialistische Relikte.

Am besten gleich alle Anwesenden wegsperren, oder? Das Verbot irgendwelcher Symbole an sich ist schon bescheuert.

Einer bringt es auf den Punkt:
Die NVA ist laut dem Justiziar der Polizei, Oliver Tölle, keine verbotene Organisation. Ihre Uniform zu tragen, sei deshalb keine strafbare Handlung. Da die NVA nicht mehr als Armee existiere, begingen die Uniformträger auch keine Amtsanmaßung.

Gegen die Abmahnung würde ich mich wehren...

Um die geht es: Traditionsverband Nationale Volksarmee.

Verweisaktualisierung

Freitag, 18. Februar 2011

Bücher


+Object Oriented Programming in C
+Denotational Semantics: A Methodology for Language Development
+Learn You a Haskell for Great Good!
-Professionelle Softwareentwicklung mit PHP 5
+Git Cheat Sheet
+Git Community Book

Geschichte


-German Deserter's War Experience
+Beeldbank
+Yad Vashem Photo Archive
+Polnische Staatsbürger - Opfer und Verfolgte unter der deutschen Besatzung
+Digitales Gedächtnis zu Orten der Zeitgeschichte
+Dresden - Adressbuch 43/44
+historische Landtagsprotokolle
+Kampfräume, Gefangenentransporte und Lager im Osten
+Regelbauten
+WW I Document Archive
-Geldscheine der DDR
+Geldscheine der DDR

KFZ


+Bowdenfix
+Classic Bike Shed
+CMS
+David Silver Spares
+Etel-Tuning ;)
-Gabriel Tachometer
-Linien von Meisterhand
+Lelebeck
+Stoßdämpferservice Technischer Handel
+Yesterdays
+Honda-Board
-Motorang (MZ)

Software


+Overlays
-tscreen
+dvtm
+tmux
-Useless Use of ... Award

Sonstiges


-Woogle
+Docs Viewer
-Keepvid
+The Pac-Man Dossier
+Edward Kmett
+Ralf Lämmel

Verweissalat 2

Freitag, 18. Februar 2011

Programmiersprachen


CoffeeScript (js)
Coherence
Frink
Gosu (jvm)
ooc
Sass (css)
StratifiedJS (js)
Thyrd
Ur

Bei Löschpedia werden gerade AliceML, Factor, Ioke, Joy, Nemerle, Pure... entfernt. Keine Relevanz für die engstirnigen Blockwarte.

Software


OPA (web)
surfraw
xzgv

Kram


Foundphotos
Genevolu (Namensverteilung)
List of cognitive biases
String Metrics
The Prime That Wasn't
Typefuck - Brainfuck in Haskell type checker
Walter Lewins Regenbögen (eng., Video)

Konferenzen 2010

Freitag, 18. Februar 2011

27C3
Emerging Languages Camp 2010 (videos)
CUFP 2010 - videos
Haskell Symposium 2010
ICFP 2010 (videos)
Principles of Programming Languages 2010 (papers)

dfa minimisation in Python

Freitag, 11. Februar 2011

Recently I stumbled upon a paper by Marco Almeida, Nelma Moreira and Rogerio Reis: Incremental DFA minimisation. Beside some minor flaws, like e.g. the missing "ICDFA" definition (already present in the predecessor: On the performance of automata minimization algorithms) and the slightly strange pseudo code, I'm still not convinced about their normalisation-function.

They argue (section 4 below listing 1.1 resp. proof of lemma 1) that this function reduces the considered pairs to n²/2 - n. If we take all pairs p,q, we obviously get n² pairs. After sorting and removing the duplicates we get (n²+n)/2 pairs, without identities (n²-n)/2...

In order to better understand some parts of the algorithm, I reimplemented it in Python. I left out most optimizations and tried to stay close to the original pseudo code. It works at least for two examples. ;)


#!/usr/bin/python3

# Implementation of the MIN-INCR ICDFA minimisation algorithm without(!)
# optimized data structures.
#
# Use minimalIncremental() from FAdo Project for your projects.


# Literature
# ----------
#
# [idm] Almeida, Moreira, Reis: Incremental DFA minimisation
# [ufa] Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm
#
#
# Links
# -----
#
# FAdo Project:
#   - http://www.ncc.up.pt/FAdo/
#   - http://fado.dcc.fc.up.pt/FAdo/


verbose = False



# ==== fake union-find ==== ([ufa])

sets = {}

def make(x):
        """creates new singleton set {x}"""
        global sets

        sets[x] = set([x])

def find_(sets,x):
        """returns representative element of set containing x"""

        for id,s in sets.items():
                if x in s:
                        return id

def find(x):
        """wrapper for find_"""
        global sets

        return find_(sets,x)

def union(p,q):
        """combines a and b"""
        global sets

        a,b = normalise(find(p),find(q))
        if a != b:
                sets[a] |= sets[b]
                del sets[b]



# ==== minimisation ==== ([idm])

neq   = set()
equiv = set()
path  = set()
dfa   = {}

# (idm L1.1)
def normalise(p,q):
        return (p,q) if p<q else (q,p)


# (idm L1.4) - just use python's set implementation
def set_make():
        return set()

def set_insert(v,s):
        s.add(v)

def set_remove(v,s):
        s.remove(v)

def set_search(v,s):
        return v in s

def set_elements(s):
        return s


# (idm L1.3)
def equiv_p(p,q):
        """tests equivalence of p and q"""
        global neq, equiv, path, dfa, verbose
        d = dfa

        print_("equiv: {0}\npath : {1}\nneq  : {2}\n".format(equiv,path,neq))

        if (p,q) in neq:
                return False

        if set_search((p,q),path):
                return True

        set_insert((p,q),path)

        for a in d['Sigma']:
                print_("p,a,q:",p,a,q)

                (p_,q_) = normalise(find(d['delta'](p,a)),find(d['delta'](q,a)))

                if p_ != q_ and not set_search((p_,q_),equiv):
                        set_insert((p_,q_),equiv)

                        if not equiv_p(p_,q_):
                                return False
                        else:
                                set_remove((p_,q_),path)

        set_insert((p,q),equiv)

        return True


# (idm Theorem 2)
def joinstates(d,classes):
        """returns new dfa based on equivalence classes"""

        Q = set(classes.keys())
        Sigma = d['Sigma']
        delta = lambda p,a: find_(classes,d['delta'](p,a))
        q0 = find_(classes,d['q0'])
        F = set(map(lambda x: find_(classes,x),list(d['F'])))

        return {'Q':Q,'Sigma':Sigma,'delta':delta,'q0':q0,'F':F}


# (idm L1.2)
def min_incr(d):
        global neq, equiv, path, dfa
        dfa = d

        for q in d['Q']:
                make(q)

        neq = set([normalise(p,q) for p in d['F'] for q in d['Q'] - d['F']])

        for p in d['Q']:
                for q in [x for x in d['Q'] if x > p]:
                        if (p,q) in neq:
                                continue

                        if find(p) == find(q):
                                continue

                        equiv = set_make()
                        path  = set_make()

                        if equiv_p(p,q):
                                for (p_,q_) in set_elements(equiv):
                                        union(p_,q_)
                        else:
                                neq |= path

        classes = {}
        for p in d['Q']:
                lider = find(p)
                classes[lider] = classes[lider] | set([p]) if lider in classes else set([p])

        print_('classes:',classes,'\n')

        return joinstates(d,classes)



# ==== I/O ====

def print_(*args):
        global verbose

        if verbose:
                print(*args)

def print_dfa(name,d):
        print('{0}\n{1}'.format(name,'='*len(name)))
        print('Q    : {0}\nSigma: {1}\ndelta:'.format(d['Q'],d['Sigma']))
        for q,a in [(q,a) for q in d['Q'] for a in d['Sigma']]:
                print(' '*6,q,a,d['delta'](q,a))
        print('q0   : {0}\nF    : {1}\n'.format(d['q0'],d['F']))



# ==== examples ====

# DFA d={q,s,d,q0,f}

def dfa_01_d(p,a):
        tab = {
                0:{'a':1,'b':2},
                1:{'a':4,'b':2},
                2:{'a':3,'b':2},
                3:{'a':4,'b':0},
                4:{'a':4,'b':4}}

        return tab[p][a]

dfa_01 = {'Q':set([0,1,2,3,4]),'Sigma':set(['a','b']),'delta':dfa_01_d,'q0':0,'F':set([4])}


def dfa_02_d(p,a):
        tab = {
                0:{'a':1,'b':4},
                1:{'a':2,'b':5},
                2:{'a':3,'b':2},
                3:{'a':3,'b':2},
                4:{'a':5,'b':0},
                5:{'a':4,'b':1}}

        return tab[p][a]

dfa_02 = {'Q':set(range(0,6)),'Sigma':set(['a','b']),'delta':dfa_02_d,'q0':0,'F':set([2,3,4])}


# ==== main ====

if __name__ == '__main__':
        print_dfa('DFA 01',dfa_01)
        dfa_01_min = min_incr(dfa_01)
        print_dfa('DFA 01 min',dfa_01_min)

        print_dfa('DFA 02',dfa_02)
        dfa_02_min = min_incr(dfa_02)
        print_dfa('DFA 02 min',dfa_02_min)


Feel free to play around with it.
(Seite 1 von 35, insgesamt 516 Einträge) » nächste Seite