Algorithm
=========

A generated identicon can be described as one big rectangle divided into ``rows
x columns`` rectangle blocks of equal size, where each block can be filled with
the foreground colour or the background colour. Additionally, the whole
identicon is symmetrical to the central vertical axis, making it much more
aesthetically pleasing.

The algorithm used for generating the identicon is fairly simple. The input
arguments that determine what the identicon will look like are:

* Size of identicon in blocks (``rows x columns``).
* Algorithm used to create digests out of user-provided data.
* List of colours used for foreground fill (foreground colours). This list will
  be referred to as ``foreground_list``.
* Single colour used for background fill (background colour). This colour wil be
  referred to as ``background``.
* Whether the foreground and background colours should be inverted (swapped) or
  not.
* Data passed to be used for digest.

The first step is to generate a *digest* out of the passed data using the
selected digest algorithm. This digest is then split into two parts:

* The first byte of digest (``f``, for foreground) is used for determining the
  foreground colour.
* The remaining portion of digest (``l``, for layout) is used for determining
  which blocks of identicon will be filled using foreground and background
  colours.

In order to select a ``foreground`` colour, the algorithm will try to determine
the index of the colour in the ``foreground_list`` by doing modulo division of
the first byte's integer value with number of colours in
``foreground_list``::

  foreground = foreground_list[int(f) % len(foreground_list)]

The layout of blocks (which block gets filled with foreground colour, and which
block gets filled with background colour) is determined by the bit values of
remaining portion of digest (``l``). This remaining portion of digest can also
be seen as a list of bits. The bit positions would range from ``0`` to ``b``
(where the size of ``b`` would depend on the digest algoirthm that was picked).

Since the identicon needs to be symmetrical, the number of blocks for which the
fill colour needs to be calculated is equal to ``rows * (columns / 2 + columns %
2)``. I.e. the block matrix is split in half vertically (if number of columns is
odd, the middle column is included as well).

Those blocks can then be marked with whole numbers from ``0`` to ``c`` (where
``c`` would be equal to the above formula - ``rows * (columns / 2 + columns %
2)``). Number ``0`` would correspond to first block of the first half-row, ``1``
to the first block of the second row, ``2`` to the first block of the third row,
and so on to the first block of the last half-row. Then the blocks in the next
column would be indexed with numbers in a similar (incremental) way.

With these two numbering methods in place (for digest bits and blocks of
half-matrix), every block is assigned a bit that has the same position number.

If no inversion of foreground and background colours was requested, bit value of
``1`` for a cell would mean the block should be filled with foreground colour,
while value of ``0`` would mean the block should be filled with background
colour.

If an inverted identicon was requested, then ``1`` would correspond to
background colour fill, and ``0`` would correspond to foreground colour fill.

Examples
--------

An identicon should be created with the following parameters:

* Size of identicon in blocks is ``5 x 5`` (a square).
* Digest algorithm is *MD5*.
* Five colours are used for identicon foreground (``0`` through ``4``).
* Some background colour is selected (marked as ``b``).
* Foreground and background colours are not to be inverted (swapped).
* Data used for digest is ``branko``.

MD5 digest for data (``branko``) would be (reperesented as hex value) equal to
``d41c0e80c44173dcf7575745bdddb704``.

In other words, 16 bytes would be present with the following hex values::

  d4 1c 0e 80 c4 41 73 dc f7 57 57 45 bd dd b7 04

Following the algorithm, the first byte (``d4``) is used to determine which
foreground colour to use. ``d4`` is equal to ``212`` in decimal format. Divided
by modulo ``5`` (number of foreground colours), the resulting index of
foreground colour is ``2`` (third colour in the foreground list).

The remaining 15 bytes will be used for figuring out the layout. The
representation of those bytes in binary format would look like this (5 bytes per
row)::

  00011100 00001110 10000000 11000100 01000001
  01110011 11011100 11110111 01010111 01010111
  01000101 10111101 11011101 10110111 00000100

Since identicon consits out of 5 columns and 5 rows, the number of bits that's
needed from ``l`` for the layout would be ``5 * (5 / 2 + 5 % 2) == 15``. This
means that the following bits will determine the layout of identicon (whole
first byte, and 7 bits of the second byte)::

  00011100 0000111

The half-matrix would therefore end-up looking like this (5 bits per column for
5 blocks per column)::

  010
  000
  001
  101
  101

The requested identicon is supposed to have 5 block columns, so a reflection
will be applied to the first and second column, with third column as center of
the symmetry. This would result in the following ideticon matrix::

  01010
  00000
  00100
  10101
  10101

Since no inversion was requested, ``1`` would correspond to calculated
foreground colour, while ``0`` would correspond to provided background colour.

Limitations
-----------

There's some practical limitations to the algorithm described above.

The first limitation is the maximum number of different foreground colours that
can be used for identicon generation. Since a single byte (which is used to
determining the colour) can represent 256 values (between 0 and 255), there can
be no more than 256 colours passed to be used for foreground of the
identicon. Any extra colours passed above that count would simply be ignored.

The second limitation is that the maximum dimensions (in blocks) of a generated
identicon depend on digest algorithm used. In order for a digest algorithm to be
able to satisfy requirements of producing an identcion with ``rows`` number of
rows, and ``columns`` number of columns (in blocks), it must be able to produce at
least the following number of bits (i.e. the number of bits equal to the number
of blocks in the half-matrix)::

  rows * (columns / 2 + columns % 2) + 8

The expression is the result of vertical symmetry of identicon.  Only the
columns up to, and including, the middle one middle one (``(columns / 2 + colums
% 2)``) need to be processed, with every one of those columns having ``row``
rows (``rows *``). Finally, an extra 8 bits (1 byte) are necessary for
determining the foreground colour.