# HEPIA LIGHTS

## Introduction

Le projet HEPIA LIGHT est un projet qui prend place pendant le cours "Atelier embarqué" en deuxième semestre de deuxième année.

Le but du projet est d'utiliser des matrices de 16x16 LEDS comme des éléments d'écran flexible. Le but est d'avoir un écran fait de plusieurs matrices de LED qui puisse change de dimensions en ajoutant ou retirant des matrices.

## Cahier des charges

Voici une liste des différentes demandes et contraintes contenues dans le cahier des charges du projet.

Pour commencer un peu de contexte, les matrices ont toutes 16*16 leds, elles ont toutes un microcontrolleur raspberry (RP2040) embarqué, elles peuvent communiquer en se branchant les unes aux autres sur les 4 faces de la carte carrée.

Voici une liste des points importants du cahier des charges :

- Chaque matrice doit contenir le même code
- On doit pouvoir ajouter des matrices pour changer la taille de l'écran, on ne peut pas hard coder les dimensions à l'avance
- On doit pouvoir brancher une des cartes de la matrice à un linux pour être contrôlé par un driver fait maison
- Le driver doit implementer un Framebuffer et permettre à nimporte quelle app de Linux d'afficher des choses sur l'écran

Voici une liste des compromis qui sont autorisés pour faciliter le développement

- On peut partir du principe que toutes les matrices seront ajoutées dans la même orientation (Ca nous permet de "hard coder" les directions cardinales pour faciliter le routing des messages)
- On peut partir du principe que la carte master est en bas à gauche de la matrice tant toutes les cartes ont le même firmware (Si on branche une autre carte elle doit aussi pouvoir être master, juste elle ne prendra pas en compte les matrices qui ne sont pas dans sa diagonale directe)
- On peut partir du principe que la matrice de matrice sera toujours rectangulaire et que on ajoute des colonnes ou des lignes entières. (Donc si on ajoute une matrice seule dans un bord et que ca ne fait plus un rectangle ca ne marchera pas)
- On aura toujours un rectangle plein, pas de trous dans la matrice

## Principe de fonctionnement

Quand on branche le coin de la matrice à notre linux, one élection très simple se fait pour determiner quelle carte est maitre et qui sont les esclaves.

![Fig 1](./Media/MasterElection.png "Election par le port USB")

Par défaut à la mise sous tension, une carte est toujours esclave. Cependant, si la carte detecte que elle est branchée (soit par detection USB soit par un paquet UART envoyé par le driver c'est encore à discuter) elle devient maitre et va pouvoir commencer le processus de découverte de ses environs.

### Decouverte automatique

#### Initialisation

Comme la carte maitre n'a techniquement aucune idée de ses entourages. Elle va créer un grand tableau de possibles et tenter de le remplir avec l'architecture réelle.

![Fig 2](./Media/GridStart.png "Grille maitre de départ")

Pour plus facilement expliquer le fonctionnement de l'algorythme on va prendre un exemple de matrice réelle rectangulaire

![Fig 3](./Media/GridReal.png "Veritable grille dans le monde réel")

On peut voir que on a une grille réelle de largeur 4 et de hauteur 3. Cela nous ferait donc 16x16x4x3 leds (4096 leds) mais evidemment l'algorythme est censé fonctionner avec une grille plus petite,plus grande, et de "facteur de forme" (ratio largeur-longeur) différent.

On peut voir que on a des connections en UART qui partent du haut et de la droite de notre carte maitre et toutes les autres cartes sont interconnectées avec des lignes UART également.

#### Découverte des côtés

Pour découvrir nos environs on pourrait penser à pleins de methodes. Comme on sait que notre matrice est rectangulaire et que elle est en principe pleine on va pouvoir utiliser une techique assez simple.

La carte master va envoyer un paquet special en haut et à droite. Ce paquet spécial va être reconnu par les cartes slaves.

![Fig 4](./Media/SlaveSideDiscovery.png "Algo simplifié de l'esclave pendant la détection des côtés")

Le but est que chaque esclave qui recoit le paquet spécial incrémente une valeur dedans et le renvoie à l'opposé de la ou elle l'a recu (Ex elle recoit le paquet depuis le bas, elle l'envoie en haut)

Si elle ne peut pas l'envoyer car il n'y a plus de voisin dans la direction. Alors c'est que on est arrivé à la fin de la ligne et donc l'esclave envoie une réponse au master avec le chiffre incrémenté qui représente le nombre de matrices connectées dans la ligne.

Comme on a pas encore de système d'adresse, il faut aussi prévoir un routage simple qui dit que quand un slave recoit un message pour le master mais que il n'a pas de position, alors il relaie simplement le message à l'opposé.

De cette facon, en principe, le master envoie un paquet à gauche et un paquet en haut et après un court délai il recoit une réponse qui lui permet de se faire une idée des dimensions de la matrice réelle.

![Fig 5](./Media/GridSideDiscovered.png "Recherche des côtés")

A part de la on peut assez facilement déduire de la véritable taille de la grille et on est donc prêt à assigner une position à toutes les cartes de la grille.

#### Assignement des positions.

##### Pourquoi faire ?

![Meme 1](./Media/PourquoiFaire.png "Omar Sy, pourquoi faire ?")

Maintenant que l'on a une idée de à quoi ressemble notre grille il va falloir assigner une position à toutes nos cartes. Pourquoi? Et bien par ce que pour la suite nous allons devoir trouver un moyen de router les instructions du master à toutes les cartes de la grille et pour cela il faut que chaque carte aie une notion de sa position dans le systeme.

Chaque carte va avoir une position X;Y qui représente sa position dans le tableau interne au master mais aussi à sa position physique dans l'espace. Cela permet de très facilement savoir ou envoyer nimporte quel information de pixel.

Imaginons notre grille de 16x16x4x3 pixels. Cela représente un écran de 64:48px Si on veut par exemple toucher au pixel 34:12 on sait que il faut l'envoyer à la carte qui se trouve en (34//16):(12//16) => 2:0. C'est super facile. Pour ce qui est des avantages au niveau routage on en parle un peu plus bas.

##### Comment faire ?

Comme on sait quelles sont les dimensions des côtés de notre matrice, on peut infèrer de à quoi ressemble toute la matrice et on peut la représenter dans un tableau de la sorte dans notre master :

![Fig 6](./Media/GridFinal.png "Etat de la grille après reconnaissance")

Sauf que pour le moment seule le master connait les positions des différentes cartes. Il va donc falloir venir dire à chaque carte quelle position elle occupe dans la matrice.

Pour ca on va y aller étape par étape ligne par ligne et colonne par colonne.

Par défaut au démarrage chaque carte est un esclave et n'a pas de position. Ensuite quand elle recoit un numéro, à moins de recevoir un paquet d'invalidation (Voir plus bas), elle le garde jusqu'à ce que elle soit éteinte.

Pour assigner les positions, le maitre va donc envoyer un paquet pour chaque carte selon le protocole de communication que l'on va voir un peu plus bas.

![Fig 7](./Media/SlaveAssignement.png "Assignement de la position")

Quand une carte recoit un paquet d'assignation, elle peut y lire l'addresse de destination. Si la carte n'a pas encore de position assignée, alors c'est que la position lui est destinée et elle peut donc prendre comme position celle du paquet. Quand elle a pris la position, elle envoie un paquet au master pour confirmer et que le master puisse savoir quand la grille est prête. Elle peut l'envoyer facilement car le Master est toujours en 0,0

Si une carte recoit un paquet qui est pour une autre carte, alors elle va l'envoyer en direction de cette dernière. Comment elle fait pour l'envoyer dans la bonne direction, on en parle aussi juste après quand on parlera du protocole de communication en detail.

##### Côté master

Du côte du master, c'est assez simple, on va envoyer un paquet d'assignation pour chaque carte en envoyer les paquets sur les deux sorties et en principe, comme les cartes choppent leurs addresses au fur et à mesure, les paquets pourront aller de plus en plus loin dans la grille. Le master n'a plus qu'à attendre les réponses de toutes les cartes pour continuer.

Si le master ne recoit pas tous les ACK au bout d'un certain temps, alors il renvoie un paquet d'assignement aux cartes qui n'ont pas répnondu. Si ca ne fonctionne pas plusieurs fois alors il invalide toute la matrice (Voir plus bas quand on parle de l'ajout d'une carte dans la grille) et il recommence le processus depuis le début en allant découvrir les côtés.

##### Resultat

En principe, après toutes ces étapes, le master a une grille interne qui repertorie la position de toutes les cartes et toutes les cartes ont une position. Le master est donc prêt à envoyer des paquets à nimporte quelle carte de la grille en fonction de son addresse et chaque carte est capable de répondre. On a donc un écran initialisé.

#### Envoi des informations de pixels

Maintenant que l'on a une carte Maitre qui sait quelles cartes sont connectées à la grille et la position de chaqune et que toutes les cartes elles mêmes savent ou elles se positionne dans la grille, on peut passer aux choses sérieuses.

Le maitre va recevoir les informations sur l'image à afficher depuis le driver linux qui communique à travers le port USB. Ensuite quand le maitre a un paquet qui contient les valeurs de 16x16 pixels et que il sait ou l'envoyer dans la matrice, il envoie le paquet sur une de ses sorties UART pour que laisser le message se propager. (Sauf dans le cas ou les leds à allumer sont celles du maitre lui même)

On a deja vu en partie le système de distribution des messages plus haut mais on va rentrer dans les détails ici.

##### Algo de distribution de messages

Voici le diagramme qui décrit le système de distribution des messages à travers la matrice :

![Fig 8](./Media/SlaveMessageProcessing.png "Propagation message")

Dans l'odre, quand un slave recoit un paquet d'information sur une de ses entrées UART :

1. Il vérifie si le message lui est destiné, si oui alors on prend en compte l'information et on envoie un paquet d'ACK en 0,0 (master) sur l'entrée ou le message est arrivé

2. Si le message ne nous est pas destiné alors on lit dans l'entête combien de paquets vont arriver pour cette destination et on les route tous vers la destination

3. Pour savoir sur quelle sortie router notre paquet, on suit l'algorythme suivant : 

- On imagine une droite diagonale qui part du coin en direction cardinale de la destination et qui continue à 45 degrés (ex pour x,y = 4;5 en partant de 2,2 la diagonale part du coin haut droite mais pour une destination de 1,3 alors que on part de 5,5 la diagonale part du coin bas gauche à 45 degrés)
- Ensuite on regarde de quel côté de cette ligne la destination se trouve et on envoie un paquet sur le côté en question.

Voici deux exemples graphiques pour se faire une meilleure idée :

![Fig 9](./Media/MessageDirection1.png "Choix de la direction 1")

![Fig 10](./Media/MessageDirection2.png "Choix de la direction 2")

Voici l'algorythme formel qui devrait permettre d'implémenter cette solution.

Soit pos.x et pos.y la position de notre matrice courante
Soit X et Y la position de destination
Soit diffX et diffY la différence absolue entre la position courante x et y et celle de la destination

On choisit d'envoyer à droite si :

- X > pos.x && diffY < diffX

On choisit d'envoyer à gauche si :

- X < pos.x && diffY < diffX

On choisit d'envoyer en haut si 

- Y > pos.Y && diffY > diffX

On choisit d'envoyer en bas si 

- Y < pos.Y && diffY > diffX

Dans les cas ou la diffX et la diffY sont les mêmes, alors on alterne en fonction de si la différence est paire ou impaire. (Si on venait à hésiter entre droit et bas, on choisirait le bas quand la différence est impaire et le haut quand elle est paire)

##### Pourquoi s'embêter comme ca?

On pourrait en voyant ca se dire que c'est un poil plus compliqué que nécessaire. En effet un algo plus simple du genre "tant que pos.y != Y alors on envoie en haut ou en bas et quand pos.y == Y alors on s'occupe de pos.x..." Ce qui serait très simple et très facile à visualiser.

C'était l'algo prévu à la base, le problème vient du fait que comme notre liaison UART est notre principal goulot d'étranglement, on veut absolument utiliser les interfaces de la manière la plus efficace possible. Donc si notre master ou les cartes proches du master peuvent utiliser le plus possible chaque entrée de manière parfaitement équilibrée cela permet de garder une transmission de données plus élevée. (Exemple, si une sortie UART permet la transmission de 1mbit/s, alors si on parvient à utiliser celle du haut et de droite de manière parfaitement équivalentes, alors on peut monter à 2mbit/s ce qui peut drastiquement changer la vitesse de rafraichissement de notre grille)

Si on y réfléchis un peu plus, on peut se dire que le gain n'est important que pour la carte maitre et potentiellement les cartes directement adjacentes, mais comme on doit avoir le même code sur toutes les cartes c'est plus simple d'utiliser le même algorythme de distribution partout.

#### Traitement des infos 

Quand on recoit un nouveau paquet du master en êtant un slave. On peut lire dans le premier byte le type de message.

Dans ces 8 bits, les 4 MSB sont les plus importants car ils determinent le type de message. Les 4 LSB sont toujours sou la forme 0101.

Voici une liste des paquets possibles pour le moment dans notre protocole

| sequence    | definition        |
| ----------- | ----------------- |
| 1000 0101   | Side Discovery    |
| 1100 0101   | SD return         |
| 0100 0101   | Slave Assignement |
| 0010 0101   | Invalidate        |
| 0001 0101   | Pixel Data        | 
| 0000 0101   | ACK               |
| 1111 0101   | Ping              |

Tous ces paquets sont forgés par le master à l'exeption des paquets ACK, Ping et SD return.

##### Side discovery (10000101 | 0x85)

Octets à suivre : 1

Structure :

On a un octet pour l'entête et un octet qui permet de garder le compte le nombre de sauts.

Marche à suivre :

1: Ping le côté opposé

2: Si on obtient une réponse :

Incrémenter le second octet de 1 et envoyer le message complet dans la direction opposée. (Ex recu côté sud on envoie au nord)

2: Si le côté opposé ne répond pas, alors on crée un paquet side discovery que on envoie sur le même côté sur lequel on a recu le paquet Side discovery.


##### Side discovery return [SD return] (11000101 | 0xC5)

Octets à suivre : 1

Structure :

On a un octet pour pour l'entête et un octet pour le compte du côté

Marche à suivre :

On le relaie à l'opposé de l'endroit ou on l'a recu. Le paquet est destiné au master et normalement il se trouve dans la direction opposée de la ou on recoit le retour.

##### Slave Assignement (01000101 | 0x45)

Octets à suivre : 2

Structure :

Byte 1: Entête
Byte 2: Position X  
Byte 3: Position Y  

Marche à suivre :

Voire marche à suivre dans "Assignement des positions" mais en gros si on a deja une position assignée on route le paquet et sinon on prend la position qui est donnée.

##### Invalidate (00100101 | 0x25)

Octets à suivre : 2

Structure :

Byte 1: Entête
Byte 2: Position X
Byte 3: Position Y

Marche à suivre :

Si le message n'est pas pour nous, on le route sinon on set notre position courante à -1,-1 (ATTENTION, ca veut dire que le maitre doit être stratège quand il veut invalider une matrice car si il le fait dans le mauvais ordre on a des paquets qui ne pourront simplement pas atteindre leur cible)

Petite variation. Avant de faire passer le message, on envoie un ping dans les deux directions possibles du paquet et on envoie dans la première qui répond. (Contrairement à la règle des pairs et impairs dans un but que le paquet aie plus de chance d'atteindre sa destination) Si personne ne répond on drop le paquet.

##### Pixel Data (00010101 | 0x15)

Octets à suivre : 16X16X3 [768] (en imaginant 8 bits par couleurs et une matrice de 16 par 16)

Si on fait un petit calcul on peut voir que avec 24bits par pixel on arrive sur des débits assez énormes... Ca fait 768 octets par seconde par carte ou 6144 bits/s par carte... Avec un lien à 1mbit/s on va pas avoir des écrans ultra rapides.

Structure :

Byte 1:  Entête
Byte 2: Position X
Byte 3: Position Y

Ensuite on traite les informations 3 octets par 3 octets

Paquet pixel :

Byte 1: Valeur de Rouge
Byte 2: Valeur de Vert
Byte 3: Valeur de Bleu

Ce qui donne : Entête->PositionX->PositionY->PaquetPixel1->PaquetPixelx...

Marche à suivre :

Si le paquet nous est destiné on traite les informations de pixel à la volée ou après avoir tout recu c'est au choix et sinon on le route normalement.

##### ACK (00000101 | 0x5)

Octets à suivre : 2

Structure :

Byte 1: Entête
Byte 2: Position X
Byte 3: Position Y

Marche à suivre :

On route le paquet vers 0,0 (Master). En principe un Esclave n'a jamais besoin de traiter un ACK, ils sont par défaut tous destinés au master. La position X,Y est la position de source et non de destination.

##### Ping (11110101 | 0xF5)

Octets à suivre : 0

Structure :

Byte 1: Entête

Marche à suivre :

Le ping est très simple et ne se comporte pas vraiment comme un ping TCP. La le but est simplement de renvoyer le paquet de la ou il vient. Il a une utilité principalement de débug ou de découverte de voisin locale. Exemple : Permettre à une matrice de savoir si une autre matrice est connectée à sa droite.

Quand on envoie un ping on garde en mémoire que on en a envoyé un et donc si on recoit un ping et que on attendait une réponse on arrête (Très important sinon on finit par juste ping en boucle)