サヴルスのブログ

Homemade regular expression matcher

2011-02-13T19:32:00.005+02:00

Here we try to build a program (all the code is provided "as is" without any warranty including but not limited to mental, psychic and wrong teaching... in short, usual open source license) that matches a string against a regular expression over simplified alphabet: base characters can be English letters only and special characters allowed are '|' (or), '*' (closure) and concatenation requires no character. All ideas given below can be found in Compilers: Principles Techniques and Tools, 2nd edition by A. Aho, M.S. Lam, R. Sethi, J.D. Ullman.

1. Basic Definitions and Notations
We give this for consistency. Reader may just skip this section

Token is a basic block of input. In our case tokens will be small letters of english alphabet and four special tokens: |, *, ( and ).
Alphabet is some set of tokens. Unless stated otherwise we assume all tokens are non-special.
String is a sequence of tokens.
Language over an alphabet is some set of strings, each sting consists of tokens from the alphabet.
Regular expressions language is a language RE over non-special and special tokens with the following properties:
1) empty string is in RE,
2) any string formed by a single non-special token is in RE.
3) if A and B are in RE, then AB, A|B, A* and (A) are in RE too.
Regular expression is an element of language RE.
Regular language L(regexp) determined by a regular expression regexp is defined as follows:
1) if regexp is an empty string, then L(regexp) contains only one string which is empty;
2) if regexp is a single token T, then L(regexp) has only one string T;
3) if regexp is of form AB where A and B are regular expressions, then L(regexp) consists of such and only such strings which can be represented as a concatenation XY of a string X from L(A) and a string Y from L(B);
4) if regexp is of form A|B where A and B are regular expressions, then L(regexp) consists of all strings from L(A) and L(B);
5) if regexp is of form (A) where A is a regular expressions, then L(regexp) is exactly L(A);
6) if regexp is of form A* where A is a regular expressions, then L(regexp) is a union of an empty string language, L(A), L(AA), L(AAA), and so on infinitely. This operation in language algebra is called Kleene closure.
Nondeterministic Finite Automata (NFA) is a triple (S,A,T) where S is a finite set of states, A is an alphabet which can contain a special empty token and T is a transitions function, which given a state and a token returns a new state. There should be chosen one starting state and some positive number of accepting states. NFA is usually depicted as a directed graph where nodes are states, and edges are labeled by tokens and edge labeled by some token X goes from a state Y to state T(Y,X). NFA is said to accept a string R if there is a directed path in the graph representing this NFA from the starting state to one of accepting states such that a string formed by edge labels with empty labels removed is exactly the R. Note, we can omit the requirement of T to be a function by saying there is some special non-accepting state Q such that all undefined transactions should go to Q.

Theorem 1 For each regular expression regexp there is an NFA that accepts strings from and only from L(regexp). Proof is done by induction on construction of regexp: NFA accepting empty string and tokens are obvious, NFA for other cases can be made using NFAs from subexpression. We will give actual constructions in the real code below.
The reverse (for every NFA there is a regular expression defining the same language) is also true. We will not need this fact later so we leave the proof for the reader.

Context-Free Grammar (CFG) is triple (T,N,P) where T is a set of terminals, N is a set of nonterminals, and P is a set of productions. Each production has a head which is always a nonterminal and a body which is a sequence of terminals and nonterminals. One of the nonterminals is designated as a start symbol.
CFG defines a language in the following way. At first we have only start symbol. Then if there are some nonterminals one is picked and substituted by a body of some production having this nonterminal as a head. We stop when there are no nonterminals left. All strings which can be derived in such a way form a language defined by this CFG.
To write down a CFG we will use a notation similar to yacc(1)'s: on each line we write a nonterminal, then ":" and then all productions having this nonterminal as a head separated by "," (we choose comma instead of yacc(1)'s pipe because it is used as RE language token and comma is absolutely vacant), the special word 'epsilon' denotes an empty production body.

Parse Tree for a string s derived using CFG G's productions is a rooted ordered tree with labels at its nodes: root is labeled by start symbol of G; each inner node corresponds to a nonterminal substitution and is labeled by that nonterminal, it's childs are labeled by terminals and nonterminals from corresponding production body in the same order. All leafs are labeled by terminals and being traversed from left to right form the string s.
Parsing is a process of constructing a parse tree from a sting.
Parser is a program capable of performing parsing.

LL(1) parsing algorithm is defined as follows. We read an input string from left to right. To represent a parse state we remember current position in the string and we have a parse stack, initially holding only a start symbol of a CFG. At each step we pop a token from the top of the stack and if it is a terminal we check if it is the same as the current token in the input. If it's not then parse error occurs, otherwise we advance the input. If the token form the stack is nonterminal we choose a production which has this token as it's head and can derive a string starting with the current input terminal. By the definition of LL(1) parser there is exactly one such production, otherwise parse error occurs.
LL(1) context-free grammar is a CFG for which LL(1) parser exists.

2. LL(1) Grammar for Regular Expressions

There is a natural CFG for the language RE obtained from the definition of RE:

S : E
E : E|T , T
T : TF , F
F : F* , R
R : (E), epsilon, L
L : q,w,e,r,t,y,u,i,o,p,a,s,d,f,g,h,j,k,l,z,x,c,v,b,n,m

Unfortunately this grammar is not LL(1) since choice between productions can't be done by looking at the current symbol only. We have to alter this grammar to make another CFG which would be LL(1) one. There are some techniques for this, namely left recursion elimination, left factoring, but we will not give them here. An LL(1) grammar for RE language got by the author is just presented without explanation.

S  :  S'
S' :  TT'
T' :  |S' , epsilon
T  :  PP'
P' :  PP' , epsilon
P  :  RR'
R' :  *R' , epsilon
R  :  (S') , epsilon , L
L  :  q,w,e,r,t,y,u,i,o,p,a,s,d,f,g,h,j,k,l,z,x,c,v,b,n,m

3. Token Class

Now that we have a grammar we can present the Token class. We have tokens for epsilon, grammar symbols and input characters.

typedef enum {
    TOKEN_EPSILON, /* empty token */
    /* nonterminals of regexp LL(1) grammar */
    TOKEN_START,   /* S  -> S' */
    TOKEN_SP,      /* S' -> TT' */
    TOKEN_TP,      /* T' -> |S'  or  epsilon */
    TOKEN_T,       /* T  -> PP' */
    TOKEN_PP,      /* P' -> PP'  or  epsilon */
    TOKEN_P,       /* P  -> RR' */
    TOKEN_RP,      /* R' -> *R'  or  epsilon */
    TOKEN_R,       /* R  -> (S')  or  a,b,c,...,z  or  epsilon */
    /*end nonterminals */
    TOKEN_NORMAL   /* token for the input character */
} TokenType;

class Token {
    TokenType type;  /* type of the token */
    char normal;     /* character for TOKEN_NORMAL token */
public:
    /* create special token of specified type */
    Token(TokenType t) : type(t) {}
    /* create  token for the specified character */
    Token(char n) : type(TOKEN_NORMAL), normal(n) {}

    bool is_epsilon() const { return type == TOKEN_EPSILON; }
    TokenType get_type() const { return type; }
    char get_char() const { return normal; }
    
    /* this is used by std::map data structure. only tokens with
     * TOKEN_NORMAL and TOKEN_EPSILON types held there */
    bool operator <(const Token& t) const { 
        if ((type == t.type) && (type != TOKEN_EPSILON))
            return normal < t.normal;
        return type < t.type;
    }
    bool operator ==(const Token &t) const {
        if ((type == t.type) && (type != TOKEN_EPSILON))
            return normal == t.normal;
        return type == t.type;
    }
};

4. NFA Class

We start with a single NFA state. The class represents the state itself and contains all transitions from this state: endpoints for the same token are grouped in vectors and tokens are used as keys in a std::map data structure. State also has a temporary bit is_on used later by algorithms to mark visited states.

class NFAState;

typedef std::vector<NFAState*> Svector;
typedef std::map<Token, Svector> ASmap;

/* Single NFA state */
class NFAState {
    private:
    ASmap moves;  /* outgoing edges of this state. */

    public:
    bool is_on; /* temporary bit to use by others */
    NFAState() : is_on(false) {}
    /* get vector of transitions for a token */
    const Svector & get_move(Token a) { return moves[a]; }
    /* get all transitions for this state */
    const ASmap & get_all_moves() { return moves; }
    /* add transition */
    void add_move(Token a, NFAState *target) {
        moves[a].push_back(target);
    }
    
};

Next is the whole NFA class. Since we only require one finish state in this program we do not support a general case by this class. However general case can be reduced to ours by simply adding a new finish state and epsilon transitions to it from old finish states. NFA class contains routines to construct a new NFA using existing NFAs. We said earlier that for every regular expression we can build a NFA accepting the same language by recursive on regular expression but we omitted actual constructs, now we give them in the code.

/* Nondeterministic Finite Automata */
class NFA {
    public:
    NFAState *start;   /* start state */
    NFAState *finish;  /* finish state */

    NFA(NFA& nfa) : start(nfa.start), finish(nfa.finish) {}
    NFA() {}

    NFA& operator=(const NFA &nfa) {
        this->start = nfa.start;
        this->finish = nfa.finish;
        return *this;
    }

    /* NFA which accepts a specified token */
    void init_token(Token t) {
        start = new NFAState;
        finish = new NFAState;
        start->add_move(t, finish);
    }

    /* NFA which accepts a string either _s_ or _t_ accepts */
    void init_or(NFA &s, NFA &t) {
        start = new NFAState;
        finish = new NFAState;
        Token epsilon = Token(TOKEN_EPSILON);

        start->add_move(epsilon, s.start);
        start->add_move(epsilon, t.start);
        s.finish->add_move(epsilon, finish);
        t.finish->add_move(epsilon, finish);
    }

    /* NFA which accepts a concatenation of _s_ and _t_ accepted strings */
    void init_concat(NFA &s, NFA &t) {
        start = s.start;
        finish = t.finish;
        Token epsilon = Token(TOKEN_EPSILON);

        s.finish->add_move(epsilon, t.start);
    }

    /* NFA which accepts a closure of _s_ */
    void init_asterisk(NFA &s) {
        start = new NFAState;
        finish = new NFAState;
        Token epsilon = Token(TOKEN_EPSILON);

        start->add_move(epsilon, finish);
        start->add_move(epsilon, s.start);
        s.finish->add_move(epsilon, finish);
        s.finish->add_move(epsilon, s.start);
    }

    /* states are allocated in heap, we need to free them explicitly */
    void delete_states() {
        Svector states, processing;
        processing.push_back(start);

        /* collect all states in the _states_ vector */
        while (!processing.empty()) {
            NFAState *p = processing.back();
            processing.pop_back();
            states.push_back(p);
            ASmap all_moves = p->get_all_moves();
            for (ASmap::iterator it = all_moves.begin(), end = all_moves.end();
                    it != end; ++it) {
                Svector &moves = (*it).second;
                for (Svector::iterator iit = moves.begin(), eend = moves.end();
                        iit < eend; ++iit) {
                    if ((*iit)->is_on) continue;
                    (*iit)->is_on = 1;
                    processing.push_back(*iit);
                }
            }
        }

        for (Svector::iterator it = states.begin(), end = states.end();
                it < end; ++it)
            delete *it;
    }
};

5. NFA Emulation

To run an NFA we first need to introduce a notion of a hyperstate. Since in NFA there can be multiple ways for a transition we need to simulate them all at once. Hyperstate is a collection of NFA states the automata can be in for the current input. Hyperstate can be constructed with the help of epsilon-closure: given a set of states, epsilon-closure is this set plus states were we can get by epsilon transitions from this set. So emulation is done as follows: initial hyperstate is the epsilon-closure of start state, each step the next hyperstate is the epsilon-closure of the set got by current token transactions from the current hyperstate. At the end of the input we check if the finish state is in current hyperstate. If it is, then NFA accepts the input, otherwise, rejects.

class NFAHyperState {
    Svector states;
    private:
    /* add all states from an NFAState with theirs's epsilon-clousure
     * which are not already in hyperstate */
    void add_closure(NFAState &s) {
        if (s.is_on) return;
        std::queue<NFAState*> Q;
        Q.push(&s);
        while (!Q.empty()) {
            NFAState *p = Q.front();
            Q.pop();
            states.push_back(p);
            p->is_on = true;
            Svector moves = p->get_move(Token(TOKEN_EPSILON));
            for (Svector::iterator it = moves.begin(), end = moves.end();
                    it < end; ++it) {
                if ((*it)->is_on) continue;
                Q.push(*it);
            }
        }
    }

    /* clear temporary markings in states. Execute after step is done */
    void clear_marks() {
        for (Svector::iterator it = states.begin(), end = states.end();
                it < end; ++it) {
            (*it)->is_on = false;
        }
    }

    public:
    NFAHyperState(NFAState *s) {
        /* add epsilon-closure of start state */
        add_closure(*s);
        clear_marks();
    }

    /* perform a single transition */
    void move(Token a) {
        Svector old; /* current hyperspace in this routine */
        old.swap(states);
        states.clear();
        /* now current hyperstate is clear, fill it using moves from
         * states in old hyperstate */
        for (Svector::iterator it = old.begin(), end = old.end();
                it < end; ++it) {
            Svector moves = (*it)->get_move(a);
            for (Svector::iterator jt = moves.begin(), jend = moves.end();
                    jt < jend; ++jt) {
                add_closure(**jt);
            }
        }
        clear_marks();
    }

    /* check if a specified NFA state is in this hyperstate */
    bool is_in(NFAState *f) {
        for (Svector::iterator it = states.begin(), end = states.end();
                it < end; ++it) {
            if ((*it) == f) return true;
        }
        return false;
    }
};

/* NFA Emulator. */
class NFAEmulator {
    private:
    NFAHyperState hyperstate;  /* all work is done here */
    NFAState *finish_state;    /* NFA finish state */

    public:
    NFAEmulator(NFA &nfa) : hyperstate(nfa.start), finish_state(nfa.finish) {}
    /* hyperstate transition */
    void move(Token a) { hyperstate.move(a); }
    /* check if NFA accepts the input */
    bool is_accepted() { return hyperstate.is_in(finish_state); }
};

6. Regular Expression Parse Tree

Now we return to our LL(1) grammar and present the parser. Since the grammar appears to be not very friendly to NFA construction operations, we have to build a parse tree first. After parse tree is constructed, build_nfa from its root can be called to construct the NFA for parsed regular expression. Routine build_nfa works by recursively generating NFA for the childs and then for the parent. Sometimes it pass an NFA generated by the one child to it's sibling. The reader is advised to draw a parse tree for some simple expression to see why this happens.

/* grammar productions */
typedef enum {
    RULE_S_SP,     /* S  -> S' */
    RULE_SP_TTP,   /* S' -> TT' */
    RULE_TP_SP,    /* T' -> S' */
    RULE_TP_E,     /* T' -> epsilon */
    RULE_T_PPP,    /* T  -> PP' */
    RULE_PP_PPP,   /* P' -> PP' */
    RULE_PP_E,     /* P' -> epsilon */
    RULE_P_RRP,    /* P  -> RR' */
    RULE_RP_ARP,   /* R' -> *R' */
    RULE_RP_E,     /* R' -> epsilon */
    RULE_R_E,      /* R  -> epsilon */
    RULE_R_LETTER, /* R  -> L */
    RULE_R_BSPB,   /* R  -> (S') */
    RULE_LETTER,   /* L  -> letter */
} GrammarRule;

class ParseTreeNode;

typedef std::vector<ParseTreeNode*> Nvector;

/* Node of a Parse tree */
class ParseTreeNode {
    GrammarRule type;       /* grammar production corresponding to this node */
    Nvector childs;         /* child nodes */
    ParseTreeNode *parent;  /* parend node */
    char letter;            /* character for RULE_LETTER type */
    
    /* nfa corresponding to this node. When constructing a prse tree this is
     * used as a parameter to _inherit_ nfa form parent or siblings */
    NFA nfa;

    public:
    /* node for a new parse tree with the starting production */
    ParseTreeNode() : type(RULE_S_SP) {}
    /* new node for existing parse tree */
    ParseTreeNode(ParseTreeNode &p) : parent(&p) {
        p.childs.push_back(this);
    }
    void set_type(GrammarRule t) { type = t; }
    void set_letter(char c) { letter = c; }
    ~ParseTreeNode() {
        for (Nvector::iterator it=childs.begin(),end=childs.end();
                it<end; ++it)
            delete *it;
        childs.clear();
    }

    /* build NFA by traversing a parse tree
     * should be called from the root of the parse tree */
    NFA & build_nfa() {
        NFA new_nfa; /* temporary NFA */
        switch(type) {
        case RULE_S_SP: /* S -> S' */
            /* NFA for this node is just the NFA for it's child */
            nfa = childs[0]->build_nfa();
            break;
        case RULE_SP_TTP: /* S' -> TT' */
            /* construct NFA for T-child and pass it to the T'-child */
            childs[1]->nfa = childs[0]->build_nfa();
            /* NFA for this node is the same as it's T-child's */
            nfa = childs[1]->build_nfa();
            break;
        case RULE_TP_SP: /* T' -> |S' */
            /* NFA is OR of inherited nfa and S'-child's NFA */
            new_nfa.init_or(nfa, childs[1]->build_nfa());
            nfa = new_nfa;
            break;
        case RULE_TP_E:
            /* NFA is right the inherited nfa, do nothing */
            break;
        case RULE_T_PPP: /* T -> PP' */
            /* construct NFA for P-child, pass it to P'-child */
            childs[1]->nfa = childs[0]->build_nfa();
            /* NFA is P'-child's nfa */
            nfa = childs[1]->build_nfa();
            break;
        case RULE_PP_PPP: /* P' -> PP' */
            /* construct concatenation NFA of inherited nfa and P-child's */
            new_nfa.init_concat(nfa, childs[0]->build_nfa());
            /* pass new_nfa to P'-childs */
            childs[1]->nfa = new_nfa;
            /* NFA is P'-child's NFA */
            nfa = childs[1]->build_nfa();
            break;
        case RULE_PP_E:
            /* NFA is inherited nfa, do nothing */
            break;
        case RULE_P_RRP:  /* P -> RR' */
            /* construct NFA for R-child and pass it to R'-child */
            childs[1]->nfa = childs[0]->build_nfa();
            /* NFA is R'-child's NFA */
            nfa = childs[1]->build_nfa();
            break;
        case RULE_RP_ARP: /* R' -> *R' */
            /* construct asterisk NFA from inherited nfa, pass it to child */
            childs[1]->nfa.init_asterisk(nfa);
            /* NFA is R'-child's nfa */
            nfa = childs[1]->build_nfa();
            break;
        case RULE_RP_E:
            /* NFA is inherited nfa, do nothing */
            break;
        case RULE_R_E:
            /* NFA is accepting only epsilon token*/
            nfa.init_token(Token(TOKEN_EPSILON));
            break;
        case RULE_R_LETTER: /* R -> L */
            /* NFA is child's NFA */
            nfa = childs[0]->build_nfa();
            break;
        case RULE_R_BSPB:
            /* NFA is S'-child's NFA */
            nfa = childs[1]->build_nfa();
            break;
        case RULE_LETTER: /* letter -> a|...|z */
            /* NFA is accepting only letter token */
            nfa.init_token(Token(letter));
            break;
        }
        return nfa;
    }
};

7. Regular Expression Parser

Now we can finally present the parser itself. LL(1) parsing algorithm has been discussed above, the only exception is that parse stack now holds not only tokens but parse tree nodes too.

typedef std::pair<Token, ParseTreeNode*> TNpair;
typedef std::vector<TNpair> TNvector;

/* Regular Expression Parser */
class REParse {
    std::string regexp;         /* regular expression to parse */
    unsigned int position;      /* current position in regexp */
    TNvector parse_stack;       /* LL(1) parse stack */
    ParseTreeNode *parse_tree;  /* parse tree */

    /* push token-node pair on a parse stack */
    void push_parse_state(Token &t, ParseTreeNode *node) {
        parse_stack.push_back(TNpair(t, node));
    }

    /* grammar production for a letter terminal in a body */
    void production(ParseTreeNode &node, GrammarRule rule, char letter) {
        node.set_type(rule);
        node.set_letter(letter);
    }
    /* grammar production with empty body */
    void production(ParseTreeNode &node, GrammarRule rule) {
        node.set_type(rule);
    }
    /* grammar production with one nonterminal in a body */
    void production(ParseTreeNode &node, GrammarRule rule, Token t1) {
        ParseTreeNode *c1 = new ParseTreeNode(node);
        push_parse_state(t1, c1);
        node.set_type(rule);
    }
    /* grammar production with two nonterminals in a body */
    void production(ParseTreeNode &node, GrammarRule rule, Token t1, Token t2) {
        ParseTreeNode *c1 = new ParseTreeNode(node);
        ParseTreeNode *c2 = new ParseTreeNode(node);
        push_parse_state(t2, c2);
        push_parse_state(t1, c1);
        node.set_type(rule);
    }
    /* grammar production with three nonterminals in a body */
    void production(ParseTreeNode &node, GrammarRule rule, Token t1, Token t2, Token t3) {
        ParseTreeNode *c1 = new ParseTreeNode(node);
        ParseTreeNode *c2 = new ParseTreeNode(node);
        ParseTreeNode *c3 = new ParseTreeNode(node);
        push_parse_state(t3, c3);
        push_parse_state(t2, c2);
        push_parse_state(t1, c1);
        node.set_type(rule);
    }

    /* can current character be the beginning of a string derieved from P' */
    bool is_first_PP(char c) const { return (isalpha(c) || (c == '(')); }
    /* can current character be the beginning of a string derieved from T' */
    bool is_first_TP(char c) const { return (is_first_PP(c) || (c == '|')); }

    /* A step of LL(1) parsing: process a token from the top of the stack */
    void process_token(Token &t, ParseTreeNode &node) {
#define T(x) Token(x)
        char lookup = regexp[position];
        switch (t.get_type()) {
        case TOKEN_START:
            production(node, RULE_S_SP, T(TOKEN_SP)); break;
        case TOKEN_SP:
            production(node, RULE_SP_TTP, T(TOKEN_T), T(TOKEN_TP)); break;
        case TOKEN_T:
            production(node, RULE_T_PPP, T(TOKEN_P), T(TOKEN_PP)); break;
        case TOKEN_P:
            production(node, RULE_P_RRP, T(TOKEN_R), T(TOKEN_RP)); break;
        case TOKEN_R:
            if (lookup == '(')
                production(node, RULE_R_BSPB, T('('), T(TOKEN_SP), T(')'));
            else if (isalpha(lookup))
                production(node, RULE_R_LETTER, T(lookup));
            else
                production(node, RULE_R_E);
            break;
        case TOKEN_TP:
            if (lookup == '|')
                production(node, RULE_TP_SP, T('|'), T(TOKEN_SP));
            else
                production(node, RULE_TP_E);
            break;
        case TOKEN_PP:
            if (is_first_PP(lookup))
                production(node, RULE_PP_PPP, T(TOKEN_P), T(TOKEN_PP));
            else
                production(node, RULE_PP_E);
            break;
        case TOKEN_RP:
            if (lookup == '*')
                production(node, RULE_RP_ARP, T('*'), T(TOKEN_RP));
            else
                production(node, RULE_RP_E);
            break;
        case TOKEN_NORMAL:
            /* check if input doesn't finish unexpectedly */
            if (position >= regexp.length()) {
                std::cerr << "Parse error: went past input" << std::endl;
                throw 10; /* ABORT */
            }
            /* this production can be used for passing throwgh
             * special tokens, in this case we have to check */
            if (lookup != t.get_char()) {
                std::cerr << "Parse error: expected '" << t.get_char()
                    << "' got '" << lookup << "'" << std::endl;
                throw 20; /* ABORT */
            }
            production(node, RULE_LETTER, lookup);
            ++position; /* all right, advance input position */
            break;
        default:
            std::cerr << "Parse error" << std::endl;
            throw 30; /* ABORT */
        }
    }

    public:
    REParse(std::string re) : regexp(re), position(0) {
        /* initialize parse tree and stack */
        parse_tree = new ParseTreeNode();
        parse_stack.push_back(TNpair(Token(TOKEN_START), parse_tree));
        /* LL(1) parsing cycle */
        while (!parse_stack.empty()) {
            TNpair& tnpair = parse_stack.back();
            parse_stack.pop_back();
            process_token(tnpair.first, *tnpair.second);
        }
        /* check if we weren't able to process all the input regexp */
        if (position != regexp.length()) {
            std::cerr << "Parse error: finished early" << std::endl;
            throw 40; /* ABORT */
        }

    }

    /* get parse tree */
    ParseTreeNode * get_parse_tree() const { return parse_tree; }

    ~REParse() {
        delete parse_tree;
    }

};

8. Epilogue

We presented all the parts to build a regular expression matcher. First we need to parse a regular expression alongside with building a parse tree, next we build an NFA from a parse tree, then we emulate NFA and finally check if NFA accepts the input string. As a final example here is the main() function of our program. It reads two string: first one is a regular expression, second is a matched string. It outputs "matched" if the input string appears to be in the language defined by the regular expression, otherwise the program outputs "not matched"

int main() {
    std::string re;
    std::cin >> re;  /* read regular expression */
    REParse parser(re);  /* parse regular expression */
    NFA nfa = parser.get_parse_tree()->build_nfa(); /* build NFA */
    NFAEmulator nfaemu(nfa); /* Initialize NFA emulator */

    std::string match;
    std::cin >> match; /* read input string */

    /* process string */
    for (unsigned int i=0; i < match.length(); ++i)
        nfaemu.move(match[i]);
    if (nfaemu.is_accepted()) std::cout << "matched";
    else std::cout << "not matched";
    std::cout << std::endl;

    /* free states allocated in heap */
    nfa.delete_states();
}

9. Further Reading

Aforementioned Compilers: Principles, Techniques and Tools contains every idea presented here. Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani and Ullman explains the mathematics behind automatas and conext-free grammars. Finally, this is a very good online resource about regular expressions in practice with parsing done by Dijkstra's shunting yard algorithm and reverse polish notation processing which is much more simpler than LL(1) parser presented here.

updatable SQL table with external ordering

2010-12-25T09:46:00.002+02:00

Nearly half a year a crucial bug was found in uguu. It was fixed that time and it haven't bothered us since then. I've always wanted to write about it here.

We store all files in a single SQL table. Each row has a path_id, and a file_id. The first is same for all files from the same directory. The second represents a (lexicographical) order on files. We assign file ids sequentially without a gap. While updating contents of a share we need to insert/delete some rows in the files table preserving the sequential order.

First solution.

To insert a row with file id N, increment ids for rows with ids >= N

UPDATE files SET file_id = file_id + 1 WHERE file_id >= N AND path_id = some_path

then insert the new row with file_id N.

Deletion is performed analogously:

DELETE FROM files WHERE file_id = N AND path_id = some_path
UPDATE files SET file_id = file_id - 1 WHERE file_id > N AND path_id = some_path

Clearly, for a directory with M files addition of K new files with ids 1,2....,K can result in O(M*K^2) time. And which is more frustrating if all changes are done in a single transaction, the amount of additional space can rise dramatically for Postgresql 8.4. The same is true for deletion.

Linear solution.

Work is done in two passes. In the first pass removed files are deleted from the table and new files are inserted into a new temporary table. In the second pass file ids are being corrected in a single loop with the help of postgresql cursors. We make loop over rows from old table and use cursor to point to current entry in the new table. After the second pass gaps in file ids in the old table are exactly ids of new files (in a temporary table). Finally, we insert everything from temporary table into old one. For an implementation of the second pass see function push_path_files here.

using template translator in binary translation system

2010-11-11T01:19:00.003+02:00

Our bosses at work asked us to give a talk about template translator (rather simple binary translation layer) at the conference. Text and slides are now available (in Russian).

a contribution

2010-08-23T12:19:00.009+03:00

It seems a little patch I sent to the btpd project more than a year ago is finally accepted: commit, original message

Evolution of uguu scanning process

2010-04-22T18:30:00.049+03:00

Scanning is very essential part of a search engine. It is about how database is filled and updated. You can't search if nothing was scanned before. In this post I'd like to cover how scanning in uguu is implemented and how it has evolved over time.

From the very start it was decided that scanning should be split between two programs. The first one connects to a share, somehow constructs a list of contents of the share and prints it to the standard output. The second one is protocol-independent script which reads contents from the standard input and executes a sequence of SQL commands to insert contents into the database. This sounded very reasonable that time since I had already written smbscan in C and I didn't want to deal with SQL in C. Python appeared to be easier for this task. Also, simple text output helps a lot with testing and debugging.

smbscan itself also consisted of protocol dependent part (connecting to a share, go up, go to subdir, readdir) and independent one (constructing file tree). When Radist (the other one uguu developer) wanted to port his ftp scanner to uguu I asked him to use tree constructor from smbscan so we could change scanner output format more easily if necessary. Later this common part evolved into libuguu.

Now it's time to turn back to the scanning process. At first we thought that when time to scan a share comes all contents of the share should be dropped from the database and the share itself should be rescanned by protocol-dependent scanner having it's output read by the database updating script. If some error occurs SQL transaction rollback is executed and scanning process is marked as failed. If the scanner report success then changes are committed to the database. All described process is done inside a single SQL transaction so there is no need to care about what our users see in the middle of scanning process - they see old version until new one is committed.

When we first launched uguu it appeared scanning was very slow. Some optimizations were required. First idea came to my mind was not to perform database updating if contents of a share were unchanged. I thought to execute diff on scanner outputs saved to files, but Radist suggested comparing only security hash digests. We started to keep SHA1 digest of the scanner output in the database and checked against it before each update. Since many shares don't change their contents often uguu gained a big speedup here.

By that time I thought "If it were possible to diff old and new scanner outputs and commit only actual changes...". But scanning speed wasn't the biggest problem anymore - we needed to improve search time next. At the beginning of April database schema change was committed and scanning became major issue again.

Next long-awaited feature was automatic recursion detection in the tree constructor. The source of the problem is that filesystem links are not always detectable by the client. Suppose you have a directory A and you create a symbolic link B in it pointed to A. Then SMB protocol client would see that B is just a plain directory and it has a subdirectory B and so on infinitely. If A has a huge subtree then it is copied each time SMB client enters B resulting very huge scanner output and of course big database workload. Solution was to calculate MD5 digest for each directory and compare against it's ancestors. If a match occurs then directory parent's MD5 is compared to that ancestor's MD5. Recursion is said to be detected if along the path to the root we find a chain of directories which MD5s are the same as of such chain moved to the end of the path (current directory) and overall number of items in that chain's directories is bigger than a certain threshold. The latter condition provides a scale for a chain size: from 1 if linked directory is large to the threshold if there is a directory with only one child - the link itself.

Recursion detection is very useful feature if there are shares with recursive links. But there are very few such shares in our environment.

The next idea was quite simple to implement: if two shares have the same SHA1 digest then keep only one copy of contents in the database. This was supposed to reduce amount of files in the database for hosts with same contents via both SMB and FTP. But in reality this wasn't very helpful since some changes can occur between SMB and FTP scanning and which is more frustrating when a filename is not good enough it is shown differently via SMB and FTP. The latter argument kicks the whole idea to the ground.

So the only last hope remained - to construct a diff against old contents. Compared to previous work this was a big task with a huge amount of new code in libuguu but it is finally done and currently is being tested on our installation.

Tree diffing is very straightforward: first the whole old tree is reconstructed from a file, then while constructing a new tree using protocol-dependent walker, tree constructor compares new contents against old ones. If a new directory is added (respectively an old one is deleted) tree constructor prints the whole subtree with prefix '+' (respectively '-'). Same goes for files. If only size or number of items in a directory (or just size in case of a file) has been changed then only the directory (file) is printed with '*' modifier. Strictly speaking, output is a bit more complex to help further processing by the database updating script.

Dullness of the algorithm can be viewed in a situation when just some directory's name has been changed and that directory has a huge subtree. Then two trees will be presented in diff (one with '-' prefix and the other with '+'). However in uguu we keep tsvector of entire path for each file to allow searching in full paths. So we would have to update the entire subtree anyway.

Now uguu has scanners for FTP, SMB and WebDAV (the latter was written last weekend and is still quite unreliable). All of them use the tree constructor from libuguu and thus have all the features described above.

PS. Thanks Radist for pointing out some errors.

simple port scanner

2010-02-08T00:00:00.011+02:00

Strange, but well-known scanning tool nmap has a quite aggressive license. It is in fact GNU GPL Version 2 but with some exceptions. Among others there is one which may force you not to use nmap in your scripts:

 * Note that the GPL places important restrictions on "derived works", yet *
 * it does not provide a detailed definition of that term.  To avoid       *
 * misunderstandings, we consider an application to constitute a           *
 * "derivative work" for the purpose of this license if it does any of the *
 * following:                                                              *
...
 * o Executes Nmap and parses the results (as opposed to typical shell or  *
 *   execution-menu apps, which simply display raw Nmap output and so are  *
 *   not derivative works.)                                                *

This is very confusing and I've decided to write my own port scanner for uguu which is BSD-licensed. Needless to say, we planned to use nmap originally. With having our own tool we strike several goals at once: no nmap license terms violation, no external program execution in our python scripts, lessen the number external parts uguu is depended on, scan a list of host-port pairs at once without grouping by ports (you can give nmap list of hosts through stdin but you can't specify ports there, afaik). And with all these advantages it was fine by me to have a scanner with less performance. But as for my small /24 network with 4 computers and no crappy firewalls it is even faster than nmap (nmap -PS -p): 3 seconds against 8 seconds.

The scanner is written in python and is available as a part of uguu codebase (bin/network.py). It can be executed as a standalone application with ip range (three formats are available: single host, ip1-ip2, ip/netmask) and port specified in command line. Ip range can't be large for now due to number of open files limitations, but it worked for me with /24 netmask.

PS. Should I pass some other options to nmap? But no cheating here, it has to be a user-invoked port scanner.

uguu - search engine for local networks

2010-01-11T10:55:00.008+02:00

I've spent new year holidays on designing and writing (alongside with another one developer) a local searcher which would allow quick search and browsing through SMB and FTP shares. For years we were using http://sourceforge.net/projects/fsmbsearch but I don't like neither it's design which almost doesn't rely on relational database (I may be wrong here and it would be interesting to find out the answer) nor it's implementation when installation requires dealing with autohell, patching some outdated version of samba and getting loads of perl modules.

The new search engine called uguu is entirely open source and is available at http://code.google.com/p/uguu. It uses libsmbclient and small amount of C code for scanning SMB share, postgres for database, python for scripts and django as web framework.
It is still very far way to go (for example, no search page yet) and there are some things I plan to do myself, but if you want to contribute in any way feel free to join google group devoted to this project: http://groups.google.com/group/uguu

Spy mode inotify

2009-10-31T17:40:00.011+02:00

Although linux inotify(7) user-space interface allows to catch events on file operations it doesn't provide a way to answer a simple question: who the hell is accessing my files. By 'who' I mean which process, of course. So if we want to get an answer for that question we have to go into kernel space. (Constantly doing 'lsof|grep' is out of question here.)

Little thinking give us a hope this can be done with quite simple kernel module. Indeed, inotify handler must be called just in the moment a file is accessed, meaning inotify handler is running in context of the process which is accessing a file. So our inotify handler can just output to dmesg desired fields from 'current' task. This should work until some sophisticated buffering is introduced between file operations and inotify handlers.

Kernel provides an easy way to use self-written inotify handler in a kernel module. See Documentation/filesystems/inotify.txt for details.

The code below just exhibits the described approach works. For trying it do

insmod spy_inotify.ko path=file_to_spy_on

Then access that file and watch dmesg for messages like the following

[spy_inotify] Catched inotify event for file ../../cpufreq.c. mask=32, pid=8183 executable="less"

spy_inotify.c

/*  spy_inotify - linux kernel `module for spying on inotify events
*  prints to dmesg _who_ exactly is doing something with a file
*
*  Copyright (C) 2009 Ruslan Savchenko
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/namei.h>
#include <linux/inotify.h>
#include <linux/sched.h>
#include <linux/string.h>

#define SPY_INOTIFY "[spy_inotify] "
#define MASK (IN_ACCESS | IN_ATTRIB | IN_CLOSE_WRITE | IN_CLOSE_NOWRITE \
| IN_CREATE | IN_DELETE | IN_DELETE_SELF | IN_MODIFY \
| IN_MOVE_SELF | IN_MOVED_FROM | IN_MOVED_TO | IN_OPEN )

static char *path = "/";
module_param(path, charp, 0);
MODULE_PARM_DESC(path, "Path to spy at");
static char comm[TASK_COMM_LEN];


void sinotify_event(struct inotify_watch *watch, u32 wd, u32 mask,
u32 cookie, const char *name, struct inode *inode);
void sinotify_destroy(struct inotify_watch *watch);


static struct inotify_operations si_op = {
sinotify_event, sinotify_destroy };


void sinotify_event(struct inotify_watch *watch, u32 wd, u32 mask,
u32 cookie, const char *name, struct inode *inode) {
task_lock(current);
strncpy(comm, current->comm, sizeof(current->comm));
task_unlock(current);
printk(KERN_INFO SPY_INOTIFY
"Catched inotify event for file %s. mask=%d, pid=%d executable=\"%s\"\n",
path, mask, current->tgid, comm);
}

static struct inotify_handle *ih = 0;
static struct inotify_watch watch;

void sinotify_destroy(struct inotify_watch *watch) {
}

int init_sinotify(void)
{
struct path s_path;
int err;

printk(KERN_INFO SPY_INOTIFY "Spying at %s\n", path);

if ((err = kern_path(path, LOOKUP_FOLLOW, &s_path)) != 0) {
printk(KERN_ERR SPY_INOTIFY "kern_path() returned %d\n", err);
goto out;
}

/* FIXME: crappy nullcheck and no actions on error. Odd */
if ((s_path.dentry == NULL) || (s_path.dentry->d_inode == NULL)) {
printk(KERN_ERR SPY_INOTIFY "NULL dentry or inode\n");
err = -ENOENT;
goto out;
}

ih = inotify_init(&si_op);
if (IS_ERR(ih)) {
printk(KERN_ERR SPY_INOTIFY "inotify_init() returned bad ptr\n");
err = PTR_ERR(ih);
goto out;
}

inotify_init_watch(&watch);

err = inotify_add_watch(ih, &watch, s_path.dentry->d_inode, MASK);
if (err < 0) {
printk(KERN_ERR SPY_INOTIFY
"inotify_add_watch() returned bad descriptor: %d\n", err);
goto clean_ih;
}

return 0;

clean_ih:
inotify_destroy(ih);

out:
return err;
}

void exit_sinotify(void)
{
inotify_rm_watch(ih, &watch);
inotify_destroy(ih);
printk(KERN_INFO SPY_INOTIFY "End spying\n");
}


module_init(init_sinotify);
module_exit(exit_sinotify);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Ruslan Savchenko");
MODULE_DESCRIPTION("Spy-mode inotify");

Makefile

obj-m += spy_inotify.o

all:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

.pathrc

2009-10-09T11:30:00.003+03:00

For a long time I've been using a 'usr' directory in my home to install additional/patched software built from scratch. It is very convenient since the main distribution keeps clean and using of environment variables makes it look like everything is normal. For some unknown reason long in the past i've moved variable initializations out of my .bashrc file to .pathrc which is presented below.

Hehe, .pathrc is not something I'm very proud about but several days ago I suddenly urged for it without having any access to my home computer. So let it be posted here.


# set PATH so it includes user's private bin if it exists
USER_PREFIX=~/usr
if [ -d ${USER_PREFIX}/bin ] ; then
    PATH=${USER_PREFIX}/bin${PATH:+:$PATH}
    export PATH
fi
if [ -d ${USER_PREFIX}/sbin ] ; then
    PATH=${USER_PREFIX}/sbin${PATH:+:$PATH}
    export PATH
fi
if [ -d ${USER_PREFIX}/include ] ; then
    C_INCLUDE_PATH=${USER_PREFIX}/include${C_INCLUDE_PATH:+:$C_INCLUDE_PATH}
    export C_INCLUDE_PATH
fi
if [ -d ${USER_PREFIX}/include ] ; then
    CPATH=${USER_PREFIX}/include${CPATH:+:$CPATH}
    export CPATH
fi
for l in lib lib64; do
    if [ -d ${USER_PREFIX}/${l} ] ; then
        LIBRARY_PATH=${USER_PREFIX}/${l}${LIBRARY_PATH:+:$LIBRARY_PATH}
        export LIBRARY_PATH
    fi  
    if [ -d ${USER_PREFIX}/${l} ] ; then
        LD_LIBRARY_PATH=${USER_PREFIX}/${l}${LD_LIBRARY_PATH:+:$LD_LIBRARY_PATH}
        export LD_LIBRARY_PATH
    fi
done
if [ -d ${USER_PREFIX}/share/man ] ; then
    # MANPATH should be ended with ":", otherwise man(1) doesn't
    # search in system paths. See manpath(1) for details.
    MANPATH=${USER_PREFIX}/share/man:${MANPATH}
    export MANPATH
fi

Writing a DMA Bootloader

2009-10-06T20:09:00.070+03:00

Preamble

At work I was asked to write a program which performs a dma transfer. After reading some documentation, articles and posts on the internet i've done it finally.Since I haven't found a tutorial for this I'll try to write one here.

Abstract

Bootloader sets up the environment for the OS kernel, loads the kernel and transfers execution to it. By using DMA mode the job of loading the kernel and other jobs can be done in parallel thus reducing boot time. Here I'll try to present a DMA mode transfer as early as possible.

Master Boot Record

First of all what is a bootloader? On startup x86 processor executes instruction at address 0xFFFFFFF0 ([3], 9.1.4 "First Instruction Executed") which is located in BIOS area ([2], 3.1.3 "BIOS Memory"). After BIOS finishes hardware checking and other jobs it loads first sector (512 bytes), called Master Boot Record, of a boot device into 0x0000:0x7c00 memory location, saves drive number into DL register and transfers execution control to 0x7c00 ([1], 6.5.1 "Booting from BAIDs"). Although it is very well known that MBR must be ended with 55 AA signature I can't find exact document proclaiming that. So bootloader is just a 510-byte length code with additional 0xaa55 (little-endian) after the end to be executed in real mode at addres 0x7c00.

It is possible to use BIOS fuctions in bootloader. They are invoked as interrupts using 'int' instruction ([3], 6 "Interrupt and Exception Handling"; [3], 16.1.4 "Interrupt and Exception Handling" in real mode; see [5] for detailed description of 'int' instruction), parameters are passed through registers (AH is typically used for selecting a function while interrupt vector selects a function class). The large reference known as Ralf Brown's Interrupt List is available on the internet (see Links). For example, to print a message one can use the following function (in NASM syntax; see Links for NASM manual):


; prints a null-terminated string pointed by DS:SI
print:  lodsb
        test al, al
        je .done
        mov ah, 0x0e   ; BIOS int 0x10/AH=0x0e function. AL = character to write
        mov bx, 0x0007 ; BH = page number, BL = foreground color
        int 0x10       ; display a character on the screen, advancing the cursor
                       ; and scrolling the screen as necessary
        jmp print
.done:  ret

BIOS can even be used for loading a sector from hdd to memory. For more details refer to Rallf Brown's Interrupt List.


        ; read from disk drive in LBA mode
        ; disk drive specified by DL is be used
        mov si, addrpacket
        mov ah, 0x42 ; BIOS int 0x13/AH=0x42 function. DL = drive number
                     ; DS:SI = disk address packet address
        int 0x13     ; performs READ from disk drive in LBA mode

Here addrpacket is a data structure stored in the main memory. In the following example addrpacket tells BIOS to transfer the second sector of the disk drive to address 0x7e00 (or DS:0x7e00, RBIL doesn't say it explicitly)


        addrpacket db 0x10   ; size of this disk address packet structure
                   db 0      ; reserved
                   dw 1      ; number of blocks to transfer
                   dd 0x7e00 ; transfer buffer in main memory
                   dd 1, 0   ; starting absolute 64-bit block number

It is up to BIOS to choose which mode the latter transfer is performed in. It could be DMA as well as PIO so we can't rely on BIOS here.

ISA DMA vs PCI IDE DMA

The idea of DMA is older than PCI. On the internet there are plenty of tutorials and examples describing ISA DMA (see Links). If you read something about two DMA controllers (8237A compatible, in particular) or I/O ports 0x00 - 0x0f, then the talk is about ISA DMA. What we need here is IDE DMA which is quite more complicated.

PCI and PCI Configuration Space

In x86 architecture there are two address spaces supported by the processor: main memory ([4], 3.3 "Memory Organization") and I/O address space which elements are called ports ([4], 13 "Input/Output"). While accessing main memory is done by 'mov' and several other instructions, I/O ports are accessed by 'in' and 'out' instructions (see [5], [6] for detailed description of these instructions)

PCI presented another address space called "PCI Configurations Space" in which each PCI device obtains a 256-byte area. PCI Configuration Space is accessed using two ports: 0x0cf8 and 0x0cfc ([8], 3.2.2.3.2 "Software Generation of Configuration Transactions"). The first one is called CONFIG_ADDRESS and the second one is called CONFIG_DATA. Configuration transaction works as follows: software writes to CONFIG_ADDRESS to specify which device's configuration register should be accessed via CONFIG_DATA. Then it reads or writes CONFIG_DATA port thus performing load to or store from device's configuration space. CONFIG_DATA is 32-bit port and 4 bytes aligned at 4-byte boundary are accessed at once.

CONFIG_ADDRESS has the following format ([8], 3.2.2.3.2 "Software Generation of Configuration Transactions")


31 30      24 23        16 15           11 10              8 7               2 1 0
+-+----------+------------+---------------+-----------------+-----------------+-+-+
| | Reserved | Bus Number | Device Number | Function Number | Register Number |0|0|
+-+----------+------------+---------------+-----------------+-----------------+-+-+
31 - Enable bit

Enable bit specifies if CONFIG_DATA will be accessed. Function Number selects a function in multi-functional device - PCI device which has separate PCI configuration space for each supported function number. For example, PIIX controller we consider later here has PCI-ISA bridge as function 0 and PCI IDE controller as function 1.

PCI Configuration space for each PCI device consists of header and device dependent region ([8], 6.1 "Configuration Space Organization"). Header is specified as follows


+----------+-------------+-------------+---------------+----------------------+
| register | bits 31-24  | bits 23-16  | bits 15-8     | bits 7-0             |
+----------+-------------+-------------+---------------+----------------------+
| 00       | Device ID                 | Vendor ID                            |
| 04       | Status                    | Command                              |
| 08       | Class code                                | Revision ID          |
| 0C       | BIST        | Header type | Latency Timer | Cache Line Size      |
| 10       | Base address #0 (BAR0)                                           |
| 14       | Base address #1 (BAR1)                                           |
| 18       | Base address #2 (BAR2)                                           |
| 1C       | Base address #3 (BAR3)                                           |
| 20       | Base address #4 (BAR4)                                           |
| 24       | Base address #5 (BAR5)                                           |
| 28       | Cardbus CIS Pointer                                              |
| 2C       | Subsystem ID              | Subsystem Vendor ID                  | 
| 30       | Expansion ROM base address                                       |
| 34       | Reserved                                  | Capabilities Pointer |
| 38       | Reserved                                                         |
| 3C       | Max latency | Min Grant   | Interrupt PIN | Interrupt Line       |
+----------+-------------+-------------+---------------+----------------------+

Here we only use Vendor ID (0x00), Status (0x06), Class Code (0x09) and BAR4 (0x20). When talking about Class Code it is often split into three bytes: base class code (0x0b), subclass code (0x0a) and programming interface (0x09) ([8], 6.2.1 "Device Identification"). Base Address Registers are used to specify mapping between either main memory or i/o space and device memory ([8], 6.2.5 "Base Addresses"). Bit 0 of BAR determines the type of memory: 0 for main memory, 1 for i/o space.

For more information see [10], 24 "The PCI Local Bus" and [8].

PCI IDE contorller

To peform DMA IDE transfer IDE controller must be capable of Bus Master function. Such device is determined as follows: base class code and subclass code must both be 0x01 to identify IDE device, and bit 7 of programming interface must be 1 to identify that the device is capable of Bus Master operation ([7], 5.0. "PCI Specifics"; [8], Appendix D "Class Codes"). PIIX/PIIX3 controller is a multi-functional PCI device and it's function 1 is exactly an IDE device with class code 0x010180 ([2], 2.3. "PCI Configuration Registers—IDE Interface (Function 1)", 2.3.6. "CLASSC - CLASS CODE REGISTER (Function 1)").

We need to use 2 bits of PCI Command register ([2], 2.3.3. "PCICMD - COMMAND REGISTER (Function 1)"):


PCI Command Register (address 0x04-0x05)
+-----+------------------------------------------------------------------------+
| bit | Description                                                            |
+-----+------------------------------------------------------------------------+
|  2  | Bus Master Enable (BME). 1 - enable, 0 - disable                       |
|  0  | I/O Space Enable (IOSE). 1 - enable access to ATA and Bus Master ports |
+-----+------------------------------------------------------------------------+

ATA ports are called Legacy IDE ports and are used for sending ATA commands. They have fixed addresses, we'll talk about them when discussing ATA part of DMA protocol. Bus Master ports have changeable base address which is configurable via BAR4.

BAR4 is called Bus Master Interface Base Address Register (BMIBA) in PIIX/PIIX3 documentation ([2], 2.3.9. "BMIBA—BUS MASTER INTERFACE BASE ADDRESS REGISTER (Function 1)"). Bits 2-15 specify 4-bytes aligned base address, bit 0 is hardwired to 1 to indicate this BAR is for I/O address space, other bits are reserved and set to 0.

The latter I/O address range is called PCI Bus Master IDE Registers ([2], 2.7. "PCI BUS Master IDE Registers") and includes the following ports:


+--------+--------------------------------------------------------------------+
| Offset | Desscripton                                                        |
+--------+--------------------------------------------------------------------+
|  0x00  | Primary Channel Bus Master IDE Command Register                    |
|  0x02  | Primary Channel Bus Master IDE Status Register                     |
|  0x04  | Primary Channel Bus Master IDE Descriptor Table Pointer Register   |
|  0x08  | Secondary Channel Bus Master IDE Command Register                  |
|  0x0a  | Secondary Channel Bus Master IDE Status Register                   |
|  0x0c  | Secondary Channel Bus Master IDE Descriptor Table Pointer Register |
+--------+--------------------------------------------------------------------+

Command and Status ports are 8-bit registers while Descriptor Table Pointer is 32-bit one. Bit 3 of Command Register is used for specifying Read/Write operation (Bus Master Read operation reads from memory, Bus Master Write operation writes to memory), bit 0 is used for Start/Stop Bus Master operation. Bit 0 of Status Register indicates if Bus Master operation is in progress, bit 1 indicates errors. For more details refer to [2], 2.7. "PCI BUS Master IDE Registers".

Bits 2-31 of Descriptor Table Pointer Register specify a 4-bytes aligned base address for Physical Region Descriptor Table. PRD Table entry has the following format ([7] 1.2. "Physical Region Descriptor"; [2], 3.5.3. "BUS MASTER FUNCTION"):


+---------+----------+----------+----------+----------+
|         |  byte 3  |  byte 2  |  byte 1  |  byte 0  |
+---------+----------+----------+----------+----------+
| dword 0 | Memory Region Physical Base Address     |0|
| dword 1 |EOT|    Reserved     |  Byte Count       |0|
+---------+---+------+----------+----------+--------+-+

Region Address is an address in main memory associated with DMA transfer. Byte Count specify the latter region size in bytes. EOT bit indicates if this PRD is the last one in the table. Note that Physical Region must not cross 64K boundary.

ATA

Legacy IDE I/O ports have constant addresses ([2], 3.5.1. "ATA REGISTER BLOCK DECODE"). They are divided into four blocks: Primary Command Block (base 0x01f0), Primary Control Block (base 03F4h), Secondary Command Block (base 0x0170), Secondary Control Block (base 0x0374). Here registers of command block are presented ([9], 6.2 "I/O register descriptions")


+--------+--------------------------------+
| offset | Register Function              |
+--------+--------------------------------+
|  0x00  | Data                           |
|  0x01  | Error / Features               |
|  0x02  | Sector Count                   |
|  0x03  | LBA bits 0-7                   |
|  0x04  | LBA bits 8-15                  |
|  0x05  | LBA bits 16-23                 |
|  0x06  | Device / Head                  |
|  0x07  | Status / Command               |
+--------+--------------------------------+

Each register is one byte length. Bit 7 of Status register is called BSY and indicates that device holds control block registers. If it is set all writes to control block registers are ignored. Bit 6 of Status register is called DRDY and indicates that device is capable of accepting a command.

To perform a DMA transfer software must do the following steps ([9], 8.6 "DMA data transfer commands")
a) The host reads the Status or Alternate Status register until the BSY bit is equal to 0;
b) The host writes the Device/Head register with the appropriate DEV bit value;
c) The host reads the Status or Alternate Status register until the BSY bit is equal to 0 and the DRDY bit is equal to 1;
d) The host writes any required command parameters to the Features, Sector Count, Sector Number,
Cylinder High, Cylinder Low and Device/Head registers;
e) The host initializes the DMA channel;
f) The host writes the command code (0xc8 for DMA Read with retry) to the Command register;

Conclusion

Given specifications are enough to perform a DMA transaction. Code with large number of comments is given below.

References

[1] BIOS Boot Specification, Version 1.01, January 1996, Compaq, Phoenix, Intel
[2] 82371FB (PIIX) AND 82371SB (PIIX3) PCI ISA IDE XCELERATOR, April 1997, Intel
[3] Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1, June 2009, Intel Corporation
[4] Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 1: Basic Architecture, June 2009, Intel Corporation
[5] Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2B: Instruction Set Reference, A-M, June 2009, Intel Corporation
[6] Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2B: Instruction Set Reference, N-Z, June 2009, Intel Corporation
[7] Programming Interface for Bus Master IDE Controller, Revision 1.0, 5/16/94, Brad Hosler, Intel Corporation
[8] PCI Local Bus Specification, Revision 2.3, March 29, 2002, PCI Special Interest Group
[9] Information Technology - AT Attachment Interface with Extensions - 2 (ATA-2), Working Draft, Revision 4c, March 18, 1996, X3T10
[10] The Indispensable PC Hardware Book, Third Edition, Hans-Peter Messmer, ADDISON-WESLEY

Links

http://wiki.osdev.org/MBR_(x86)
http://wiki.osdev.org/Memory_Map_(x86)
http://wiki.osdev.org/PCI
http://wiki.osdev.org/BIOS
http://wiki.osdev.org/RBIL
http://wiki.osdev.org/ISA_DMA
http://www.nasm.us/doc - NASM manual
http://www.ata-atapi.com/hiwchs.html - CHS to LBA translation
http://www.bswd.com/cornucop.htm - links to ata/atapi specfications drafts
http://www.cs.cmu.edu/~ralf/files.html - BIOS interrupts
http://www.osdever.net/tutorials/lba.php - an example of data transfer in PIO mode
http://www.nondot.org/sabre/os/articles/TheBootProcess - articles about booting and bootloader examples
http://www.freebsd.org/doc/en_US.ISO8859-1/books/developers-handbook/dma.html - ISA DMA explanation

The Code

This code works under qemu. Just save all files, run make and execute 'qemu -hda hdd' command. You should see a message "Hello world from DMA Bootloader" indicating everithing goes well.

loader.asm


;
; DMA Bootloader
;
; This program is provided as an example for educational
; purpose ONLY and WITHOUT ANY WARRANTY
; 
; Copyright 2009, Ruslan Savchenko

;------------------------------------------------
; macroses
;------------------------------------------------

%macro PCI_CONF_READ 1-2
; %1 - pci address register base
; %2 - pci conf register num
        mov eax, %1
        %ifnum %2
        or ax, %2
        %endif
        call pci_conf_read
%endm

%macro PCI_CONF_WRITE 1-2
; WARNING! mangles ebx!
; %1 - pci address register base
; %2 - pci conf register num
        mov ebx, %1
        %ifnum %2
        or bx, %2
        %endif
        call pci_conf_write
%endm

;------------------------------------------------
; consts 
;------------------------------------------------

%define iobase 0xff0     ; Bus Master I/O port base
%define sector 57        ; Number of sector to load. Must be less than 256
%define codestart 0x500  ; address where load sector to

;------------------------------------------------
; code
;------------------------------------------------

        org 0x7c00 ; tell NASM this code is to be executed at address 0x7c00

start
        ; configure stack at first
        cli                     ; disable interrupts 
        mov ax, 0x9000          ; stack segment base
        mov ss, ax              ; write segment base to SS register
        mov sp, 0xffff          ; stack pointer
        sti                     ; enable interrupts

        
        ; Loop through all PCI devices and their functions
        ; to find IDE Bus Master

        mov cx, 0xffff               ; Bus Number, Devce Number and
                                     ; Register Number together occupy
                                     ; 16 bits of PCI CONFIG_ADDRESS
        mov ebx, 0x80000000          ; set Enable bit
.m1   
        PCI_CONF_READ ebx            ; load Device ID and Vendor ID to eax
        cmp ax, 0xffff               ; check if device is not present
        je .m2                       ; device not present
        PCI_CONF_READ ebx, 0x08      ; load class code, subclass code and
                                     ; prog interface to eax
        shr eax, 15
        cmp eax, 0x010180 >> 7       ; check if class = 0x01,
                                     ; subclass = 0x01 and 
                                     ; bit 7 of prog_if = 1
        jne .m2                      ; not an IDE Bus Master device
        ; found Bus Master capable IDE controller
        mov dword [pciide], ebx      ; save CONFIG_ADDRESS to access
                                     ; IDE Bus Master in future
.m2
        add ebx, 0x100               ; try next function/device/bus 
        loop .m1
        
        mov eax, iobase | 1               ; Bus Master Interface Base Address
        PCI_CONF_WRITE [pciide], 0x20     ; save address to BMIBA Register

        PCI_CONF_READ [pciide], 0x04      ; PCI Command register
        or ax, 1                          ; set I/O Space Enable Bit
        PCI_CONF_WRITE [pciide], 0x04     ; save PCICMD


        ; wait while ATA device is bisy
        mov dx, 0x01f7          ; ATA Primary Status/Command
.m3
        in al, dx
        cmp al, 0x80            ; check if BSY bit is set
        jae .m3

        ; for Primary device set use of Drive 0 (Master) in LBA mode
        mov dx, 0x01f6          ; ATA Primary Device/Head
        mov al, 0x40            ; LBA mode, Drive = 0, LBA 27-24 = 0
        out dx, al

        ; wait for ATA defice to accept command
        mov dx, 0x01f7          ; ATA Primary Status/Command
.m4
        in al, dx
        and al, 0xc0            ; BSY and DRDY bits
        cmp al, 0x40            ; check if BSY=0, DRDY=1
        jne .m4

        ; Set parameters of transaction:
        ; nubmer of sectors, first sector LBA address and mode
        ;
        ;mov dx, 0x01f2         ; ATA Primary Sector Count
        ;mov al, 1              ; count = 1
        ;out dx, al
        ;
        ;mov dx, 0x01f3         ; ATA Primary LBA 0-7
        ;mov al, sector         ; LBA 0-7 = sector 
        ;out dx, al
        ;
        ;mov dx, 0x01f4         ; ATA Primary LBA 8-15
        ;mov al, 0              ; LBA 8-15 = 0 
        ;out dx, al             
        ;
        ;mov dx, 0x01f5         ; ATA Primary LBA 16-23
        ;mov al, 0              ; LBA 16-23 = 0
        ;out dx, al             
        ;
        ;mov dx, 0x01f6         ; ATA Primary Device/Head
        ;mov al, 0x40           ; LBA mode, Drive= 0
        ;out dx, al
        ;
        ; Using loop here reduce code size by 12 bytes
        
        mov cx, 5               ; 5 iterations
        mov dx, 0x01f2          ; ATA Primary Sector Count
        mov si, atasector       ; transaction parameters array 
        cld                     ; string operations will increase SI
.m5
        lodsb                   ; load next byte to al and increase SI
        out dx, al              ; write byte to corresponding ATA Primary
                                ; Command Block port
        inc dx                  ; increase DX
        loop .m5

        ; initialize host dma transfer
        PCI_CONF_READ [pciide], 0x04      ; PCI Command Register
        or ax, 4                          ; enable Bus Master Function
        PCI_CONF_WRITE [pciide], 0x04     ; save PCICMD

        ; set Drive 0 DMA Capable in Bus Master IDE Status Register
        ; This bit does not affect hardware operation
        ;mov word dx, iobase | 0x2         ; Bus Master IDE Status Register
        ;in al, dx
        ;or al, 0x20                       ; set Drive 0 DMA Capable
        ;out dx, al                        ; save Bus Master IDE Status

        ; write PRD Table pointer
        xor eax, eax
        mov ax, prd
        mov dx, iobase | 0x4            ; Bus Master IDE Descriptor
                                        ; Table Pointer Register
        out dx, eax

        ; command ATA to perform DMA transfer
        mov dx, 0x01f7                  ; ATA Primary Status/Command
        mov al, 0xc8                    ; DMA Read With Retry Command
        out dx, al

        ; tell Bus Master to start DMA transfer
        mov dx, iobase                  ; Bus Master IDE Command Register
        mov al, 9                       ; Start/Stop Bit set
                                        ; Read/Write Bit set
        out dx, al

        ;
        ; Place to do some other job while sector is transfered from
        ; drive to memory without holding CPU
        ;

        ; wait until transfer is finished
        mov dx, iobase | 0x2            ; Bus Master IDE Status Register
.m6
        in al, dx
        bt ax, 0                        ; Bus Master IDE Active Bit
        jc .m6

        ; transfer execution to recently loaded code
        jmp (codestart >> 4):0

;------------------------------------------------
; functions 
;------------------------------------------------

pci_conf_read
; Input:
;        EAX = PCI CONFIG_ADDRESS
; Output:
;        EAX = PCI CONFIG_DATA
        mov dx, 0xcf8           ; CONFIG_ADDRESS
        out dx, eax
        mov dx, 0xcfc           ; CONFIG_DATA
        in eax, dx
        ret

pci_conf_write
; Input:
;        EAX = DATA
;        EBX = PCI CONFIG_ADDRESS
; Output:
;       EBX = DATA
        xchg eax, ebx
        mov dx, 0xcf8           ; CONFIG_ADDRESS
        out dx, eax
        mov dx, 0xcfc           ; CONFIG_DATA
        mov eax, ebx
        out dx, eax
        ret

;------------------------------------------------
; data
;------------------------------------------------

        ; array of bytes to be passed through ATA I/O ports
        atasector       db 1, sector, 0, 0, 0x40
                        ; sector count = 1
                        ; LBA 0-7 = sector
                        ; LBA 8-15 = 0
                        ; LBA 16-24 = 0
                        ; device/head = 0x40 (LBA mode, drive 0)

align 4
        ; Physical Region Descrptor
        prd             dd codestart    ; Memory Region
                        dd 0x80000200   ; EOT, 512 bytes

        ; buffer to save CONFIG_ADDRESS of PCI IDE device
        pciide          dd 0

;------------------------------------------------
; Space for Partition Table
;------------------------------------------------

        times 436-($-$$) db 0xff

;------------------------------------------------
; boot sector magic end
;------------------------------------------------

        times 510-($-$$) db 0
        dw 0xAA55               ; MBR Signature

sector.asm


;------------------------------------------------
; code
;------------------------------------------------

        org 0x500 ; tell NASM to assume this program
                  ; begins at 0x500 when loaded into memory

start:
        mov si, hellomsg
        call print_si
 
        cli  ; disable interrupts
        hlt  ; infinite loop which can be broken only by interrupt

;------------------------------------------------
; functions 
;------------------------------------------------

print_si
        push ax
        push bx
.next
        lodsb
        test al, al
        je .done
        mov ah, 0x0e   ; BIOS int 0x10/AH=0x0e function. AL = character to write
        mov bx, 0x0007 ; BH = page number, BL = foreground color
        int 0x10       ; display a character on the screen, advancing the cursor
                       ; and scrolling the screen as necessary
        jmp .next

.done:
        pop bx
        pop ax
        ret

;------------------------------------------------
; data
;------------------------------------------------

        hellomsg db 'Hello World from DMA Bootloader', 13, 10, 0

;------------------------------------------------
; sector end
;------------------------------------------------

        times 512 -($-$$) db 0

Makefile


hdd: loader sector
        rm -f hdd
        dd if=loader of=hdd bs=512 count=1
        dd if=sector of=hdd bs=512 count=1 seek=57

loader: loader.asm
        nasm loader.asm
sector: sector.asm
        nasm sector.asm

clean:
        rm -f hdd loader sector

Known Issues

If BIOS sets DS to nonzero value the code fails. Add initializing DS to zero at the very start to ensure the code is correct.
This code doesn't check for _any_ errors. If you want to add error checks refer to corresponding documentation.
No DMA timing configuration is done. Doing this can improve transaction speed significantly. UDMA Mode 5 is 6 times faster than UDMA Mode 0.
On DMA transfer completion controller sends an interrupt. This also should be taken care of.
After issuing a DMA transfer command to device one would probably want to wait until device is ready. In this case add the following code before setting Start/Stop bit of Bus Master Command Register. But be careful and read [9] before for this standard doesn't enfocrce setting DRQ here


        ; wait until ATA device is ready to transfer data
        mov dx, 0x01f7                  ; ATA Primary Status/Command
.m7
        in al, dx
        test al, 0x08                   ; check if DRQ bit is set
        jz .m7

LANG vs LC_MESSAGES in man(1) error messages

2009-08-08T14:12:00.009+03:00

At first I'd like to say that I'm pretty happy with english being my system's language. But since I have to use russian sometimes I've set LANG=ru_RU.UTF-8. Unfortunately man(1) error messages are encoded in KOI8-R so they look like garbage on my locale. I don't particularly want them to be in russian so I've set LC_MESSAGE=C. The man page locale(1P) says:


  LC_MESSAGES
              Determine the locale that should be used to  affect  the  format
              and contents of diagnostic messages written to standard error.

But it doesn't work for man(1). After little investigation I've learned that man(1) uses catgets(3) to get an error string. The catalog descriptor for catgets(3) is received from catopen(3) which (in case $LC_MESSAGES=C) carefully tries to open /usr/share/locale/C and some other dirs with C locale and finally fallbacks to /usr/share/locale/ru. If man(1) obtains an empty string from catgets(3) it looks for it in builtin table which is what I need.
As for now I can't say which part of this complicated situation is buggy, so I've inserted a hack into man(1) to get an error string right from builtin table if the locale is C or POSIX.
Here is my patch.


diff -rNu a/man-1.6f/src/gripes.c b/man-1.6f/src/gripes.c
--- a/man-1.6f/src/gripes.c     2006-11-21 22:53:44.000000000 +0300
+++ b/man-1.6f/src/gripes.c     2009-08-11 10:36:08.000000000 +0400
@@ -99,15 +99,22 @@
 static char *
 getmsg (int n) {
        char *s = "";
-
-       catinit ();
-       if (catfd != (nl_catd) -1) {
-               s = catgets(catfd, 1, n, "");
-               if (*s && is_suspect(s))
-                       s = "";
-       }
-       if (*s == 0 && 0 < n && n <= MAXMSG)
-               s = msg[n];
+    char *lm;
+    
+    lm = getenv("LC_MESSAGES");
+    if (lm && (!strcmp(lm, "C") || !strcmp(lm, "POSIX"))) {
+           if (0 < n && n <= MAXMSG)
+                   s = msg[n];
+    } else {
+        catinit ();
+        if (catfd != (nl_catd) -1) {
+            s = catgets(catfd, 1, n, "");
+            if (*s && is_suspect(s))
+                s = "";
+        }
+        if (*s == 0 && 0 < n && n <= MAXMSG)
+            s = msg[n];
+    }
        if (*s == 0) {
                fprintf(stderr,
                        "man: internal error - cannot find message %d\n", n);

IRC DCC auto leacher

2009-02-24T11:59:00.007+02:00

Long ago in 2007 I wrote an irssi script to leach many packs from xdcc bots automaticaly. It's quite unfinished (ugly ui, etc) but I dind't touch it for ages although i'm still using it as it is. It supports downloading from only one bot at a time. If downloading breaks it will retry after timeout. Note that some bots hate if you retry right after a failure and they will ban you (sometimes waiting for more than 5 minutes is required).

Interfase is like this:

/xdccget queue [botname] [packs...] - you should start with this. After a minute xdccget will start leaching.
/xdccget add [packs...] - add more packs
/xdccget del - delete last pack
/xdccget pause - stop downloading, remove timers
/xdccget resume - resume downloading

here is the script:


#  2007, savrus
#
# Advanced downloader from xdcc bot. Independent on bot's language
#
# Based on XDCCget by Stefan "tommie" Tomanek
#
# Dustributed under GNU GPL v2 or higher

use vars qw($VERSION %IRSSI);
$VERSION = "20070321";
%IRSSI = (
    authors     => "savrus",
    contact     => "go to hell",
    name        => "xdccget",
    description => "auto download from xdcc bot",
    license     => "GPLv2",
    changed     => "$VERSION",
    commands    => "xdccget"
);

use Irssi;
use vars qw(@g_queue $g_nick $g_server $g_witem $g_timer);

sub show_help() {
    my $help="xdccget $VERSION
/xdccget queue Nickname  ...
    Queue the specified packs of the server 'Nickname'
/xdccget help
    Display this help
";
    print CLIENTCRAP $help;
}

sub sig_dcc_closed {
    my ($dcc) = @_;
    my ($dir,$file) = $dcc->{file} =~ m,(.*)/(.*),;

    return unless $dcc->{type} eq 'GET';
    return unless $dcc->{nick} eq $g_nick;

    if ($dcc->{transfd} < $dcc->{size}) {
        process_queue($dcc->{nick});
    }
    else {
#        rename $dcc->{file}, "/ircdone/$file";
        shift_queue($dcc->{nick});
        process_queue($dcc->{nick});
    }
}

sub cmd_xdccget {
    my ($args, $server, $witem) = @_;
    my @arg = split(/ /, $args);

    if ($arg[0] eq 'queue'){
        shift @arg;
        initialize_queue("@arg", $server, $witem);
    }
    elsif ($arg[0] eq 'add'){
        shift @arg;
        add_to_queue(@arg);
    }
    elsif ($arg[0] eq 'del'){
        dell_from_queue();
    }
    elsif ($arg[0] eq 'pause'){
        pause();
    }
    elsif ($arg[0] eq 'resume'){
        resume();
    }
    elsif ($arg[0] eq 'help') {
        show_help();
    }
    else {
        print CLIENTCRAP "xdccget: $g_nick @g_queue";
    }
}

sub pause {
    $nick = $g_nick;
    clean();
    $g_nick = $nick;
}

sub resume {
    process_queue();
}

sub shift_queue {
    shift @g_queue;
}

sub clean {
# Clean previous job
    if ($g_nick) {
        my $nick = $g_nick;
        $g_server->command("MSG $g_nick xdcc remove");
        $g_nick = "";
        $g_server->command("DCC close get $nick");
    }
    if ($g_timer) {
        Irssi::timeout_remove($g_timer);
    }
}

sub initialize_queue {
    my ($args, $server, $witem) = @_;
    my @args = split(/ /, $args);

    clean();

    $g_nick = $args[0];
    shift @args;
    @g_queue = @args;
    $g_server = $server;
    $g_witem = $witem;
    
    process_queue();
}
 
sub process_queue {
    while ((@g_queue[0] <= 0) && (scalar @g_queue > 0)) {
        shift @g_queue;
    }
    if (scalar @g_queue > 0) {
        $g_timer=Irssi::timeout_add(60 * 1000, 'transfer', undef);
    }
}    

sub transfer {
    Irssi::timeout_remove($g_timer);
    $g_server->command("MSG $g_nick xdcc send @g_queue[0]");
}

sub add_to_queue {
    my (@args) = @_;
    push @g_queue, @args;
}

sub dell_from_queue {
    pop @g_queue;
}

Irssi::signal_add('dcc closed', 'sig_dcc_closed');
#
# TODO: handle rejoining the channel (self disconnection + auto reconnection)
# Be careful: content may be changed in such situation.
#
#Irssi::signal_add('channel joined', 'sig_channel_joined');


## Used in a modified script for a bot that was always disconnecting from the channel.
## But be careful - usually this happens when bot owner shuffles the packlist
#
#sub sig_message_join {
#    my ($server, $channel, $nick, $addr) = @_;
#    if ($nick eq $g_nick){
#        print CLIENTCRAP "XDCCGET DEBUG: $nick joined channel (wait for $g_nick)";
#        $g_server->command("MSG $g_nick xdcc remove");
#        $g_server->command("DCC close get $g_nick");
#        if ($g_timer) {
#            Irssi::timeout_remove($g_timer);
#        }
#        resume();
#    }
#}
#Irssi::signal_add_last('message join', 'sig_message_join');


Irssi::command_bind('xdccget', \&cmd_xdccget);

print CLIENTCRAP '%B>>%n '.$IRSSI{name}.' '.$VERSION.' loaded';

mplayer screenshot name

2009-02-23T15:53:00.008+02:00

About a year ago a friend of mine complained of the filename style for screenshots by mplayer. He said it should contain the original file name and a timestamp (so one could easily watch screenshoted scene once again). I hacked mplayer but unfortunately the patch didn't get accepted to the mainline.

Here is the patch anyway:


Index: libmpcodecs/vf_screenshot.c
===================================================================
--- libmpcodecs/vf_screenshot.c (revision 28346)
+++ libmpcodecs/vf_screenshot.c (working copy)
@@ -22,9 +22,19 @@
 #include "libswscale/swscale.h"
 #include "libavcodec/avcodec.h"
 
+#include "m_option.h"
+#include "m_struct.h"
+
+#include "mplayer.h"
+
+#define SHOT_FNAME_LENGTH 102
+#define TIMESTAMP_LENGTH 20
+
 struct vf_priv_s {
     int frameno;
-    char fname[102];
+    char *fname;
+    char *basename;
+    int style;
     /// shot stores current screenshot mode:
     /// 0: don't take screenshots
     /// 1: take single screenshot, reset to 0 afterwards
@@ -36,7 +46,7 @@
     AVCodecContext *avctx;
     uint8_t *outbuffer;
     int outbuffer_size;
-};
+} vf_priv_dflt;
 
 //===========================================================================//
 
@@ -92,14 +102,65 @@
     else return 0;
 }
 
-static void gen_fname(struct vf_priv_s* priv)
+static void gen_fname(struct vf_priv_s* priv, double pts)
 {
-    do {
-        snprintf (priv->fname, 100, "shot%04d.png", ++priv->frameno);
-    } while (fexists(priv->fname) && priv->frameno < 100000);
-    if (fexists(priv->fname)) {
-        priv->fname[0] = '\0';
-        return;
+    char *base = "shot";
+    char tstamp[TIMESTAMP_LENGTH];
+    char ts_sep;
+    uint32_t hour = (uint32_t) (pts/3600);
+    uint32_t min  = (uint32_t) (pts/60) % 60;
+    uint32_t sec  = (uint32_t) pts % 60;
+    uint32_t msec = (uint32_t) (pts*100) % 100;
+    size_t n;
+
+    switch (priv->style) {
+    case 1:
+    case 2:
+        ts_sep = (priv->style == 1) ? ':' : '-';
+        /* TIMESTAMP_LENGTH is enough for 2^32 seconds */
+        snprintf(tstamp, TIMESTAMP_LENGTH,
+                  "%02" PRIu32 "%c%02" PRIu32 "%c%02" PRIu32 ".%02" PRIu32,
+                   hour, ts_sep, min, ts_sep, sec, msec);
+
+        if (priv->basename)
+           base = priv->basename;
+        else {
+            if (strstr(filename, "://"))
+                base = "shot";
+            else {
+                base = strrchr(filename, '/');
+                if (base == NULL) 
+                    base = filename;
+                else
+                    base++;
+            }
+        }
+
+        /* 8 is length of ".[].png" plus '\0' */
+        n = strlen(base) + strlen(tstamp) + 8;
+        priv->fname = malloc(n);
+        if (!priv->fname) {
+            mp_msg(MSGT_VFILTER,MSGL_ERR,"Unable to allocate memory in vf_screenshot.c\n");
+            return;
+        }
+        snprintf(priv->fname, n, "%s.[%s].png", base, tstamp);
+        break;
+    default:
+    case 0:
+        priv->fname = malloc(SHOT_FNAME_LENGTH);
+        if (!priv->fname) {
+            mp_msg(MSGT_VFILTER,MSGL_ERR,"Unable to allocate memory in vf_screenshot.c\n");
+            return;
+        }
+        do {
+            snprintf (priv->fname, SHOT_FNAME_LENGTH, "shot%04d.png", ++priv->frameno);
+        } while (fexists(priv->fname) && priv->frameno < 100000);
+        if (fexists(priv->fname)) {
+            free(priv->fname);
+            priv->fname = NULL;
+            return;
+        }
+        break;
     }
 
     mp_msg(MSGT_VFILTER,MSGL_INFO,"*** screenshot '%s' ***\n",priv->fname);
@@ -196,11 +257,13 @@
     if(vf->priv->shot) {
         if (vf->priv->shot==1)
             vf->priv->shot=0;
-        gen_fname(vf->priv);
-        if (vf->priv->fname[0]) {
+        gen_fname(vf->priv, pts);
+        if (vf->priv->fname) {
             if (!vf->priv->store_slices)
               scale_image(vf->priv, dmpi);
             write_png(vf->priv);
+            free(vf->priv->fname);
+            vf->priv->fname = NULL;
         }
         vf->priv->store_slices = 0;
     }
@@ -263,6 +326,8 @@
     av_freep(&vf->priv->avctx);
     if(vf->priv->ctx) sws_freeContext(vf->priv->ctx);
     if (vf->priv->buffer) free(vf->priv->buffer);
+    if (vf->priv->fname) free(vf->priv->fname);
+    if (vf->priv->basename) free(vf->priv->basename);
     free(vf->priv->outbuffer);
     free(vf->priv);
 }
@@ -278,7 +343,7 @@
     vf->draw_slice=draw_slice;
     vf->get_image=get_image;
     vf->uninit=uninit;
-    vf->priv=malloc(sizeof(struct vf_priv_s));
+    if (!vf->priv) vf->priv = calloc(1, sizeof(struct vf_priv_s));
     vf->priv->frameno=0;
     vf->priv->shot=0;
     vf->priv->store_slices=0;
@@ -294,14 +359,27 @@
     return 1;
 }
 
+#define ST_OFF(f) M_ST_OFF(struct vf_priv_s,f)
+static const m_option_t vf_opts_fields[] = {
+    {"style", ST_OFF(style), CONF_TYPE_INT, 0, 0, 2, NULL},
+    {"basename", ST_OFF(basename), CONF_TYPE_STRING, 0, M_OPT_MIN, M_OPT_MAX, NULL},
+    {NULL, NULL, 0, 0, 0, 0, NULL}
+};
 
+static const m_struct_t vf_opts = {
+    "screenshot",
+    sizeof(struct vf_priv_s),
+    &vf_priv_dflt,
+    vf_opts_fields
+};
+
 const vf_info_t vf_info_screenshot = {
     "screenshot to file",
     "screenshot",
     "A'rpi, Jindrich Makovicka",
     "",
     screenshot_open,
-    NULL
+    &vf_opts
 };
 
 //===========================================================================//
Index: DOCS/man/en/mplayer.1
===================================================================
--- DOCS/man/en/mplayer.1       (revision 28346)
+++ DOCS/man/en/mplayer.1       (working copy)
@@ -7180,15 +7180,28 @@
 .RE
 .
 .TP
-.B screenshot
+.B screenshot[=style:basename]
 Allows acquiring screenshots of the movie using slave mode
 commands that can be bound to keypresses.
 See the slave mode documentation and the INTERACTIVE CONTROL
 section for details.
-Files named 'shotNNNN.png' will be saved in the working directory,
-using the first available number \- no files will be overwritten.
 The filter has no overhead when not used and accepts an arbitrary
 colorspace, so it is safe to add it to the configuration file.
+.RSs
+.IPs <style>
+0: Files named 'shotNNNN.png' will be saved in the working directory,
+using the first available number \- no files will be overwritten.
+.br
+1: Files named 'basename.[hh:mm:ss.ms].png' will be saved in the
+working directory.
+.br
+2: Files named 'basename.[hh-mm-ss.ms].png' will be saved in the
+working directory. Use this if your environment doesn't allow colon
+in filenames.
+.IPs <basename>
+Basename for a screenshot file. If not set and mplayer is playing a file,
+the file name will be used. If not set and mplayer is playing a stream,
+"shot" will be used.
 .RE
 .
 .TP
Index: mencoder.c
===================================================================
--- mencoder.c  (revision 28346)
+++ mencoder.c  (working copy)
@@ -115,6 +115,7 @@
 char* audio_lang=NULL;
 char* dvdsub_lang=NULL;
 static char* spudec_ifo=NULL;
+char* filename=NULL;
 
 static char** audio_codec_list=NULL;  // override audio codec
 static char** video_codec_list=NULL;  // override video codec
@@ -397,7 +398,6 @@
 double v_timer_corr=0;
 
 m_entry_t* filelist = NULL;
-char* filename=NULL;
 
 int decoded_frameno=0;
 int next_frameno=-1;

pam_setquota, pam_kill

2008-11-18T12:55:00.011+02:00

Being network administrator at MSU dorm two years ago, I made a public ssh server. Users were presented in mysql database on another server, so I used pam_mysql and libnss_mysql, which were already existed, for my public ssh server. I also wanted to set disk quota automatically for each user, but linux setquota(8) doesn't allow you to edit quota for non-existing user. Nor did work any pam_setquotas I found. So I wrote a one myself.

Of course, I edited limits.conf. But it didn't save from stupid cpu-intensive "while(1);" programs some nasty users had left running. I decided to kill every user's process, if he/she is no longer logged on the system, and wrote pam_kill for that.

Today, to share my old code, I created two Google Code projects: pam-setquota and pam-kill. You can access them via my Google Code profile.

crc32

2008-11-15T17:06:00.017+02:00

Long time passed since my last play with crc32. I wanted to learn and benchmark zlib's implementation as well (it's quite complex in comparison to basic ones), but it seems it will stuck in my todo list for ages. So, I decided to write what I know right now.

This is a very simple implementation taken from rhash (rhash.sourceforge.net). Every article about crc32 describes the code below, it is not something outstanding from rhash.

unsigned get_crc32(unsigned crcinit, const char *p, int len) {
  register unsigned crc;
  const char *e = p + len;
    
  for(crc=crcinit^0xFFFFFFFF; p<e; p++) 
    crc = crcTable[(crc^ *p) & 0xFF] ^ (crc >> 8);
  return( crc^0xFFFFFFFF );
}

And this is an x86 asm code, produced by gcc 4.1.2 from the 'for' loop:

.L11:
        movsbl  (%ecx,%esi),%eax
        incl    %ecx
        xorl    %edx, %eax
        andl    $255, %eax
        shrl    $8, %edx
        xorl    crcTable(,%eax,4), %edx
        cmpl    %ebx, %ecx
        jne     .L11

One of my friends found a bit faster implementation written in inline asm and used it for his hash checker ArXSum. I will not give here his code, because my optimization of rhash code is even faster. ArXSum just gave me an idea to use 8-bit registers to get rid of the andl instruction.
First, I enforced gcc to use 8-bit register. I hoped it would be enough, but it won't.

unsigned get_crc32(unsigned crcinit, const char *p, int len) {
  register unsigned crc;
  unsigned char m;
  const char *e = p + len;
  m = 0;
    
  for(crc=crcinit^0xFFFFFFFF; p<e; p++) { 
    m = (crc^ *p);
    crc = crcTable[m] ^ (crc >> 8);
  }
  return( crc^0xFFFFFFFF );
}

The code produced is

.L11:
        movzbl  (%ecx,%esi), %eax
        incl    %ecx
        xorb    %dl, %al
        movzbl  %al, %eax
        shrl    $8, %edx
        xorl    crcTable(,%eax,4), %edx
        cmpl    %ebx, %ecx
        jne     .L11

Do you see that utterly useless second movzbl? My final optimization was just to remove it and to add "xorl %eax,%eax" before the loop (that would be "m = 0" which had been lost by gcc). Newest version of gcc also produces the same code.

I still want to carefully look into zlib one day and to compare their high-level optimization with mine. I will eventually post about it.

gcc optimizer

2007-10-29T22:43:00.005+02:00

I found that the following code causes segfault when compiled with -O2. Compiler:
gcc (GCC) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)


#include <stdlib.h>

struct prime {
        struct prime *next;
};

int main(){
        struct prime primes = {.next=NULL};
        struct prime *p = ℙ

        while (p->next != NULL){
                p = p->next;
        }
        p->next = (struct prime*) malloc (sizeof(struct prime));
        return 0;
}

2007-10-14T21:51:00.000+03:00

I've just started a new blog. I'll try to keep it clean and for my own accomplishments only.