Modifications restant a faire:

a/ l faut introduire une fonction C4_main() et centraliser 
les messages d'erreurs dans C4_main() pour permettre
d'implementer facilement la fonction 'est-ce que la cellule est synthetisable>
Il faut en particulier intervenir dans C4-check() ET dans C4_topologie()

b/ ajouter dans C4-check les verifications evidentes sur la befig :
une seule sortie, pas de registre, pas de bus, pas de signaux internes.

c/ il faut ajouter les transistors correspondant aux buffers dans C4_lofig()

*************************************************************************

A/ Organisation Generale du programme C4
----------------------------------------

Le programme C4 est organise en quatre grandes fonctions 
qui sont appelees successivement :

1) la fonction C4_chekk() prend une befig en entree 
et verifie qu'elle est synthetisable par C4.
Elle renvoie un index : 0 si la cellule n'est pas synthetisable
			1 si la cellule est inverseuse
			2 si la cellule est non inverseuse

2) la fonction C4_lofig() prend une befig synthetisable en entree
ainsi que l'index renvoye par C4_check(). Elle effectue une normalisation
et un reordonnancement de l'ABL (iintroduction d'operandes fictifs pour
que tous les operateurs OR et AND soient d'arite impaire), elle construit
la lofig et retourne un pointeur de lofig.

3) la fonction C4_topologie() prend en entree une befig synthetisable et la
lofig correspondante. Elle effectue un placement symbolique et un routage
symbolique des segments horizontaux ALU1 correspondant aux signaux internes 
et aux sorties (sur 3 pistes dans la zone N et 3 pistes dans la zone P). 
Si la cellule est routable, elle renvoie un pointeur sur une c4fig contenant 
une liste d'instances et une liste de segments.
Elle renvoie NULL si la cellule n'est pas routable.

4) la fonction C4_layout() prend en entree une C4fig pour le gabarit SXLIB, 
ainsi qu'un index indiquant le type de buffer a utiliser en sortie.

B/ Analyse des principaux algorithmes
-------------------------------------

NORMALISATION / REORDONNANCEMENT

Cet algorithme prend un abl quelconque ne contenant que des OR et des AND
et renvoie un abl dont toutes les sous-expressions sont d'arite impaire, 
en introduisant des operandes fictifs correspondant a des coupures.
On utilise les proprietes de commutativite des operateurs AND et OR pour
re-ordonner certaines sous-expressions de facon a maximiser
les configurations du type
- frere-frere : ... a b *) (* c d ...
- pere-fils :   (* (* a b ..

La fonction ordonne()
- Recoit une expression ABL qui sera modifiee.
         un entier "DIRECTION" 1 pour "GAUCHE" -1 pour "DROITE"
- renvoie un entier : Le nombre d'operandes fictives aux extremites
de l'expression:
0: (...) toutes les sous expressions sont d'arite impaires.
1: (* ...) ou (... *)
2: (* ... *)
        ATTENTION 
        On ne se soucie QUE des extremites de l'expression
        L'operande fictif put etre a l'interieur d'une sous expression !
        Ex : ( (*+a+b) .c.d)
Par exemple Ordonne(ABL,GAUCHE) renverra:
0 pour (...)
1 pour (* ...) ou ( (*..) ..) etc...
2 pour (* ... *)
Mais   ne renverra jamais (... *)

on utilise en particulier deux variables:
d, lextremite vers laquelle on voudrait voir des operandes fictifs des
sous expressions.
etat, le resultat de ordonne sur une sous expression.

Si ABL est un ATOME: renvoie 0; Fin de l'appel.
Sinon:
d=DIRECTION;
Pour chaque sous expression :
etat=ordonne(sous expression, d)
        si etat=0 ajoute sous expression a la liste "zero"; fin si;
        si etat=2 idem avec la liste "deux" ; fin si;
        si etat=1 idem liste "un"; 
                        d=-d; 
                        fin si;

Apres, on reconstruit ABL en mettant "bout a bout" ses expressions, et 
en veillant a maximiser les possibilites de regroupement avec des sous
expressions "soeurs". On utilisera des listes intermediaires "gauche"
et "droite" les expressions ne contenant pas d'operandes fictifs seront
systematiquement places "au millieu" de l'expression.

Mieux vaut

( (*..*) (*..)(..*)(*..) (..)(..) (..*) )
que
( (*..*) (*..)(..*)(*..)(..*) (..)(..) )
puisque l'on denombrera autant de coupure, mais celle de "droite" pourra
jouer dans une configuration FF auquel cas, on gagnera une coupure.

Cette reconstruction se fera a l'aide de deux listes de sous expressions ; 
"gauche" et "droite". Les sous expressions de type (...) etant 
systematiquement placees "au millieu" de l'expression.
Pour savoir si l'on doit mettre la derniere sous expression de type (...*)
a l'autre extremite, on compare DIRECTION et d. S'ils sont egaux,
il faut recuperer cette derniere sous expression.

Enfin, suivant le contenu des listes "gauche" et "droite", de l'entree
"DIRECTION" et de l'arite de l'expression "ABL", on renverra un entier
(0,1 ou 2) et on ajoutera eventuelement un operande fictif en tete ou en
queue d'expression.

Exemple :

s=(b+c).(d+e).(f+(g.(h+(i.j))))

Donne :

s=(*+c+b).(e+d+*).(*+(*.(*+(*.j.i)+h).g)+f) et retourne 1.

ATTENTION !
Il ne faut pas faire apparaitre d'operandes fictifs dans une expression
d'arite impaire meme si ses sous expressions en possedent.
Car lors de la generation d'un schema en transistors, la disposition en
parallele de reseaux demande d' "alterner" l'orientations des reseaux
(signaux UP et DOWN) or dans le cas d'operandes surnumeraires, on retombe
dans le cas d'une LOFIG qui ne peut correspondre avec l'ordre etabli des
entrees.


On trouvera la fonction dans ordonne.c .h
*********************************************************************
Deuxieme Partie: NETLIST

Travail a faire
 la fonction netlist() prend un abl normalise en entree
(cet abl peut contenir des operandes fictifs) et construit
la lofig correspondante. 
Les operandes fictifs n'apparaissent evidemment pas dans la lofig.

Pour etre plus precis, netlist prends une Befig en entree.
Nous avions remarque, par rapport au corrige de l'examen, qu'il etait
necessaire d'alterner le sens des sous reseaux lorsqu'ils sont
mis en parallele.
On ajoutera a cela qu'il faut inverser ce sens meme apres lecture d
un operande fictif, sinon, on obtient le meme probleme : Le schema en
transistors ne peut correspondre a l'ordre etabli des entrees. 
Si ce n'etait pas necessaire, ca voudrait dire qu'il n'y a pas
de coupure de diffusion... Pour la "Normalisation" de l'ABL, on doit
en tenir compte. 
Enfin, la prise en compte des operandes fictifs ne se fait pas des
le debut de l'appel des fonctions CreateN et CreateP mais seulement
lors de la mise en parallele ou en serie des sous reseaux.
Et ce, pour permetre l'"alternance" enoncee plus haut, et eviter la 
generation de signaux surnumeraires.

*********************************************************************
Troisieme Partie PROJECTION:

Travail a faire:

3/ la fonction projete() parcoure un abl normalise en
profondeur d'abord et construit les deux tableaux BandeN et BandeP
correspondant aux deux bandes de transistors N et P 
(avec representation explicite des coupures).
Les colonnes correspondent aux variables d'entree et aux coupures,
les lignes correspondent aux signaux (VSS, VDD, sortie, et signaux 
internes aux reseaux N et P)
La fonction projete() utilise le resultat de la fonction netlist()
pour remplir les deux tableaux, en placant les contacts dans ces tableaux.

C'est fait.
L'objet s'appele projection (voir projete.c .h)
Si j'ai le temps, j'essaierai de faire une structure projection qui
contiendrait les deux bandes. Pour minimiser les parametres. 
J'aurai du y penser plus tot !
J'ai ajoute une fonction qui renverse completement les tableaux...
projection *symproj(projection *);
Elle sert dans la derniere partie.
La structure d'une bande est assez simple:

typedef struct projection
{
struct projection       *NEXT;
char                    *NAME;
losig_list              *gauche;
losig_list              *droite;
} projection

Attention elle peut contenir un operateur fictif. C'est pourquoi projete()
ne se fonde pas seulement sur le resultat de netlist() mais aussi de
ordonne() ou de normalise()

**********************************************************************
Quatrieme partie : ROUTAGE.

Travail a faire:
4/ la fonction route() prend les deux tableaux BandeN et BandeP en entree
et construit le tableau Grid representant la grille de routage.
Ce tableau a 10 lignes et N+M+1 colonnes. N est le nombre d'entrees,
M est le nombre de coupures.
La principale difficulte est de respecter le budget de pistes de routage
horizontales : 4 pistes dans la zone des transistors N / 4 pistes dans
la zone des transistors P.

Cette fois ci, la structure generee est tres differente. Elle m'a semblee
plus simple :
On a une structure instance qui contient
un nom
un tableau de dix entiers (contacts oui/non 1/0)
un tableau de dix signaux 
l'instance suivante.

typedef struct instance
{
struct instance         *NEXT;
char                    *NAME;
losig_list              *segments[10];
int                     contacts[10];
} topologie;


On considere que la position des bandes de diffusion est implicite :
Il y a diffusion sur les 4 premires et derniers lignes de chaque
instance SAUF si l'instance s'appele "*" (ABL_FICTIVE).
En fait, a l'aide de cette topologie, on pourra construire "colonne par
colonne" la PHfig, alor qu'avec un tableau de 10 lignes et N+M+1 colonnes
classique, il aurait ete autrement plus dur de cerner la structure voulue.

Les projections et topologies commencent et finissent toujours par une
entree fictive.
C'etait plus pratique pour moi... Surtout dans le cas d'un retournement
de projections :
Au debut de la fonction route, on regarde si tous les contacts avec la sortie
sont tous a droite. Dans ce cas uniquement on inverse completement l'ordre des
Bandes N et P;
On pourra l'implementer directement dans projete.c quand la structure
projection englobera les DEUX bandes.

Il reste une chose a faire, placer correctement les "pistes" pour les
entrees. Afin d'augmenter la longeur des "segments verticaux". Je me 
reservais cette rejouissance pour la fin, car la place gagne n'est pas enorme
(elle pourrait l'etre s'il y avait beaucoup de coupures on a minimise
leur nombre).
En revanche, dans cet esprit, j'ai voulu placer les segments par ordre de taille decroissante (sortie comprise). Et faire en sorte que le signal de sortie soit le moins long possible (Pour ca j'ai la certitude, qu'on peut encore gagner
de la place, mais si peu !).

La generation de la PHfig devra se faire ainsi:
1 Placer le buffer a gauche.
2 Ignorer le premier terme de la topologie (Entree fictive)
3       Pour chaque element de la topologie (TOPO=TOPO->NEXT etc...) placer
        un transistor et les bandes de diffusion s'il s'agit d'une entree
        "classique" et placer une coupure de diffusion si le nom
        de l'instance est ABL_FICTIVE ("*").
        Apres, placer les segments suivant le tableau segments et placer les
        contacts la ou contacts[i] ne s'annule pas.
On a un exemple de Topologie effectue sur NEO655.

C/ Arbre d'instanciation des fonctions
--------------------------------------

C4_main()
	C4_check()
		C4_test_NOT()
		C4_expr_AND_OR()
		C4_pas_de_double()
	C4_lofig()
		C4_ordonne()
			C4_ordonne_aboute()
			C4_ordonne_addablexpr() 
		C4_netlist()
			C4_netlist_createN()
			C4_netlist_createP()
			C4_netlist_putin()
	C4_topologie()
		C4_projete()
		C4_topo_route()
		C4_topo_genereseg()
	C4_layout()
