It has been one month that the third year (called Ing1) of EPITA started and this is a recap of the interesting projects that I developed.

malloc (1 week)
The goal of this mini-project is to improve our knowledge of memory management by implementing the C standard library memory allocator (malloc, free, realloc). Implementation using the Binary Buddy technique:

  • List of free blocks of size 2^k.
  • Split and Merge using adjacent block of the same size called buddy.
  • Insertion and Deletion in O(log n).
  • 32 & 64 bit ready.

find (1 week)
find is a very well known UNIX command used to satisfy research upon files and directories.

  • File listing and options parsing with error handling.
  • -name: Filtering using globbing.
  • -newer, -atime, -size, -inum, -type, -links: Filtering off information sources. Handles -/+ for "less/more than".
  • -perm: Filtering based on permission expressed in octal (0777) or symbolic (u+rwx,go=r) notation.

fnmatch (10 hours)
fnmatch is a function that implements globbing. It returns whether the string matches the pattern. This is mainly used to filter out files (eg: *.txt) or text search in databases (eg: LIKE '%Text%').

  • *: any character 0 or more times.
  • ?: any character 1 time.
  • [abcA-Z]: any character from the class.
  • \*: escaping.

Libstream (10 hours)
I/O functions are slow hence they should be called few time as possible. This is why they are typically buffered. The project is to recode all the I/O buffered functions of the C standard library as they are defined by the Single UNIX Specifications V3.

  • fopen, fclose, fgetc, fputc, fflush: Core functions to handle buffered I/O at a character level.
  • fseek, ftell, frewind: File positioning functions.
  • fread, fwrite, fgets, fputs, fgetdelim: Helper functions to use buffered I/O at a string level.
  • tinyPrintf: Basic string formatting (%d, %u, %s, %c, %o, %x without modifiers).

Comparison

In Javascript there are 3 types we are often comparing: String, Number and Boolean. After digging through the ECMA-262 specifications, here is the behaviour of the == operator (11.9.3) on these types:

  • Number == String
    Typecasted as follow: Number == Number(String)
  • Number == Boolean
    Typecasted as follow: Number == Number(Boolean)
  • String == Boolean
    Typecasted as follow: Number(String) == Number(Boolean)

This means that when comparing data of two different types, they will first be converted to Number.

Note: The order of the equality is not important: A == B is the same as B == A (except the order of evalution of A and B).

You can force comparison of a and b with the type you want:

  • String: "" + a == "" + b
  • Number: +a == +b
  • Integer: a | 0 == b | 0
  • Boolean: !!a == !!b

Addition / Concatenation

The binary + operator follows a simple rule (11.6.1):

  • if one of the operands is a String, both operands are converted to String and the + is a concatenation.
  • Else, both operands are converted to Number and the + is an addition.

Note: Some Objects are considered as Strings like Arrays. See 8.6.2 for more informations.

Note: The operator is binary so 1 + 1 + 'a' will be executed as (1 + 1) + 'a' and therefore be equal to "2a" and not "11a".

Javascript is a very flexible language, I made a compilation of some edge cases that you may have encountered while programming. The main goal is to point out some interesting specific behaviors.

Concatenation

1] var result = [10] + 1;
Explanation:
The Array doesn't have a toNumber method, instead it has a toString method: [10] + 1 becomes "10" + 1.
String has a greater priority over Number with the + operator: "10" + 1 becomes "10" + "1" = "101"
2] var result = ['a', 'b', 'c'] + "";
Explanation:
The Array.toString method concatenates all it's elements (converted to string) with the "," separator.
3] var result = 'a' + 5;
Explanation:
In Javascript, String has a greater priority than Number for the + operator, so 5 is converted to string before being concatenated.
In PHP, the + operator is only the addition so 'a' is converted to number (gives 0) before being added.
In C, a char and an integer are of the same type. 'a' is first converted to it's Ascii value (gives 65) before being added.

Operations

4] var result = 3.75 | 0;
Explanation:
|0 is a fast way to do a Math.floor for positive integers.
5] var result = 65 / 'a';
Explanation:
/ is only defined for Numbers so 'a' is first converted to a number (gives 0).
A division by 0 does not throw an error but results the object NaN (Not a Number).

Objects

6] var ob = {"10": 1};
ob[10] = 2;
ob[[1, 0]] = 3;
var result = ob["10"] + ob[10] + ob[[1, 0]];
Explanation:
Objects keys are strings. If you don't provide a string, it will convert the key to string.
"10" and 10 gives "10"
[1, 0] gives "1,0"
7] var $ = {"": String};
var result = !!$[([])]();
Explanation:
$ is a valid variable name.
Parenthesis inside the key part are useless: array[(1+2)] is the same thing as array[1+2].
Objects key are first converted to string. [].toString() is "".
It is possible to have the empty string "" as an object key.
$[""] is the String object. String(val) returns val.toString(). String() returns "".
! is the negation operator. "" == false, so !"" == true, !!"" == false
!!expr is a fast way to typecast an expression to a boolean.

Equality

8] var result = (' \t\r\n ' == 0);
Explanation:
Unlike PHP, strings wrapped around simple quote ' are also parsed. '\t' == "\t"
When compared to a number value, a string will be converted to a number. If it contains only spacing characters it will be converted to 0. If a string cannot be parsed as a number it will return NaN (Note that NaN != NaN).
9] var a = new String("123");
var b = "123";
var result = (a === b);
Explanation:
When creating an object with the new operator, the result type is always "object". The type of "123" is "string" so the type does not match for ===.
10] var a = {key: 1};
var b = {key: 1};
var result = (a == b);
Explanation:
Object comparison is only done with the pointers behind the objects.


While on holidays, I played that old (bought in the 80's) board game called Fief. After several games I wanted to point at the good and bad things about this game in order to find some general rule.

Fief - Board Strategy Game

Fief - Board Strategy Game

Some assets of the game are innovative and worth mentioning.

The resources are really limited. It is common to have limited number of soldiers or houses, but the limitations are often relative to a player. In this game, there is a limited amount of money. After several rounds, there's no money left in the bank and people cannot earn their income. This opens the possibility to organize bankruptcy.

Movement design is clever. The only way to move your army from town to town are Lords. They are special soldiers that can walk 2 towns a round. While moving, they are able to carry any amount of soldiers with them. Once they are well positioned, the Lords allow you to move around the map really fast.

    However, that's not a perfect game, the main problem could be summarized with the statement "10 pages rules book". Here are some consequences of that fact.

    • Many rules leads to contradictions and unclear statements
    • The learning curve is disastrous
    • More time spent reading and discussing the rules than playing the game

    In order to find a solution, we are going to analyze some facts and get general rules off them.

    Could we play without this rule? Yes. Drop it.

    In the game, there are 2 types of building that gives resources: Mill [cost 300, give 200] and Press [cost 200, give 100]. Basically, you first buy all the Mills and when there are no left you start taking Presses. These two buildings are just about the same, do not give any kind of reflexion but have to be learned by the players. Removing one building would not affect the decision range of the user and would make the game easier to play.

    Ten things doing slightly different things? Merge them!

    There are lots of cards but you can never use them. There are offensive cards and their respective defensive cards. Offensive cards are targeted against a player and aren't that common. No need to say that you never have the defensive card when needed. That's about the same for cards that gives money, you either have to be Clergy, have a Fief or be King to use them. Since most of the time you are nothing, these cards are trash. Being given useless card over useless card is a really bad feeling.

    A solution would be to transform these useless cards would be to make them generic. What about having a rare card that can counter any offensive attack. As for the money card, it would give money based on the highest rank you have. By changing how to attribute the cards, we could keep the same usage rate. They would be seen like a great reward and as a side effect simplify the game.

    Simple rules, great flexibility.

    The methodology adopted by the game is: "There's a problem? Add a special rule for this exact problem". What if we let the user the possibility to do it anyway? It will give flexibility and make the game easier to understand! For further thoughts about this philosophy in the web development, i would suggest you to read the free book Getting Real.

    Mysqli Wrapper is shortening the code required to run queries, make them 100% safe against SQL Injections and gives a handy Array as result. No more pain writing queries!

    You can view the source at the MysqliWrapper Github Repository.

    When developing a PHP application, SQL queries is the most dangerous area. This is because the built-in tools are either not secure by conception or too much complicated to use. I've made a little wrapper to mysqli that solves all these problems and make you enjoy writing queries!

    You are probably writing your queries like this. We assume we have $zip(string) and $pop(int) variables previously declared in the code.

    // Basic Method
    mysql_connect('host', 'user', 'pass');
    mysql_select_db('database');
    $query = "SELECT Name, CountryCode FROM City 
        WHERE Zip = '".mysql_real_escape_string($zip)."' AND Population > ".(int) $pop;
    $result = mysql_query($query);
    while ($row = mysql_fetch_array($result)) {
        // $row['Name'], $row['CountryCode']
    }

    With this method, you have to secure all the fields yourself. To do it, you have to type the loooong function mysql_real_escape_string and you must not forget the quotes around the parameter. The code is unreadable, not safe by concept because you may forget to sanitize a field ... And, it is annoying to write!

    Mysqli was intended to be a wrapper around Mysql that would provide safe queries. You may wonder why this has not become the default way to write queries. Have a look at the exact same code written with mysqli.

    // Mysqli Method
    $mysqli = new mysqli('host', 'user', 'pass', 'database');
    $query = "SELECT Name, CountryCode FROM City WHERE Zip = ? AND Population > ?";
    if ($stmt = $mysqli->prepare($query)) {
        $stmt->bind_param('si', $zip, $pop);
        $stmt->execute();
        $stmt->bind_result($name, $code);
        while ($stmt->fetch()) {
            // $name, $code
        }
        $stmt->close();
    }

    Yes, 10 lines to make a SELECT. Obviously they failed to design an easy to use API. It is also too restrictive: you have to assign a variable for each of the field you want to select. This seems to be a really waste of time: it's already in the query, why would you write it another time? Also, that's not possible to use '*' to select all the fields.

    Here is my attempt to easily to write and safe queries:

    // My method
    $db = new dbWrapper('host', 'user', 'pass', 'database', true);
    $result = $db->q("SELECT Name, CountryCode FROM City WHERE Zip = ? AND Population > ?",
      'si', $zip, $pop);
    foreach ($result as $key => $city) {
      // $city['Name'], $city['CountryCode']
    }

    What's good about this:

    • A single 6 characters function
    • Secure because parameterized
    • Returns an Array
    • Easy migration from the basic method

    I'm really happy with that wrapper. It is faster to write the queries because you don't have to sanitize the parameters neither you have to think about safety and there's only a 6 character function to remember. The code is smaller and easier to use because it returns a real Array! Also, this allows to display mysql errors on the development server only and doesn't requires to type or die(mysql_error()); everytime.

    If you don't know by advance the number of parameters (A custom search where field may be selected or not by the user for example), this implementation becomes really tricky to deal with. I have no solution at this time for this problem. The v8cgi Query API would handle this problem really well, however i am not confident enough in letting a script writing my queries.

    The wrapper code is really hacky but fits in 60 lines so can be embedded really easily. Download

    Class dbWrapper {
        protected $_mysqli;
        protected $_debug;
     
        public function __construct($host, $username, $password, $database, $debug) {
            $this->_mysqli = new mysqli($host, $username, $password, $database);
            $this->_debug = (bool) $debug;
            if (mysqli_connect_errno()) {
                if ($this->_debug) {
                    echo mysqli_connect_error();
                    debug_print_backtrace();
                }
                return false;
            }
            return true;
        }
     
        public function q($query) {
            if ($query = $this->_mysqli->prepare($query)) {
                if (func_num_args() > 1) {
                    $x = func_get_args();
                    $args = array_merge(array(func_get_arg(1)),
                        array_slice($x, 2));
                    $args_ref = array();
                    foreach($args as $k => &$arg) {
                        $args_ref[$k] = &$arg; 
                    }
                    call_user_func_array(array($query, 'bind_param'), $args_ref);
                }
                $query->execute();
     
                if ($query->errno) {
                  if ($this->_debug) {
                    echo mysqli_error($this->_mysqli);
                    debug_print_backtrace();
                  }
                  return false;
                }
     
                if ($query->affected_rows > -1) {
                    return $query->affected_rows;
                }
                $params = array();
                $meta = $query->result_metadata();
                while ($field = $meta->fetch_field()) {
                    $params[] = &$row[$field->name];
                }
                call_user_func_array(array($query, 'bind_result'), $params);
     
                $result = array();
                while ($query->fetch()) {
                    $r = array();
                    foreach ($row as $key => $val) {
                        $r[$key] = $val;
                    }
                    $result[] = $r;
                }
                $query->close(); 
                return $result;
            } else {
                if ($this->_debug) {
                    echo $this->_mysqli->error;
                    debug_print_backtrace();
                }
                return false;
            }
        }
     
        public function handle() {
            return $this->_mysqli;
        }
    }

    Update February 17 2010: Now works for php >= 5.3.0. Added debug_print_backtrace to get the sql query when there is an error.