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
Second to fourth workspace: switch master and focus
Fifth workspace (for browsing): keep master and focus and use tabbed layout (open new links/tabs in background)
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.

¹ last one: the bookmark menu needs 30s to load all bookmarks
² webserver(!), torrent- and unusable mail client
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.

¹ 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
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
Gleich nach Deutschem Kreuz und Ritterkreuz oder wie? m(
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
Montag, 15. August 2011
UNO bekräftigt das Recht auf Gotteslästerung
Da haben die Sekten wohl vergessen einige Posten zu unterwandern.
General Comment No. 34
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 Insiderberichte von Mobbing und vom Abschneiden vom Informationsfluss, sobald man sich als Laizist zu erkennen gibt, scheinen also zu stimmen.
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.
Die SPD ist eh unwählbar, ob die jetzt auch noch die Kirche als Parteiführung haben, spielt keine Rolle mehr.
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:
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:
strtod():

png floating point:

Papers you might be interested in:
¹ No, I still don't know their definition of "non-positive".
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():

png floating point:

Papers you might be interested in:
- A. Kiezun, V. Ganesh, P. J. Guo. HAMPI: A Solver for String Constraints
- C. Cadar, D. Dunbar, D. Engler. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs
- D. Ramos, D. Engler. Practical, low-effort equivalence verification of real code
- F. Yu, T. Bultan, M. Cova, O. Ibarra. Symbolic String Verification: An Automata-based Approach
¹ No, I still don't know their definition of "non-positive".
33. Kirchentag
Sonntag, 5. Juni 2011

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.

Man machte auch keinen Hehl daraus:

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:

Jesus mit Fahrrad:

Martin Luther höchstpersönlich:

Ökopolitik:

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

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.

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)
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
Neben Wulff mit von der Partie: Annette Schavan, Franz Josef Jung, Volker Kauder und Ursula von der Leyen.
Staat stützt Kirchen mit Milliarden
Sekten und Geldwäsche:
Glasnost bei der Vatikanbank?
Sekten und Missbrauch:
Belgian child abuse report exposes Catholic clergy
Missbrauchsopfern droht der Maulkorb
"Auffälligkeiten" und Vertuschungen
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
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:
Dass Text und Zitat nicht zusammen passen ignorieren wir mal:
Am besten gleich alle Anwesenden wegsperren, oder? Das Verbot irgendwelcher Symbole an sich ist schon bescheuert.
Einer bringt es auf den Punkt:
Gegen die Abmahnung würde ich mich wehren...
Um die geht es: Traditionsverband Nationale Volksarmee.
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
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.
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.