Pourquoi est-ce notable ? « Parce que les performances de ces langages sont deux mondes différents », vous me direz ? Eh bien... pas tant que ça, en fait. Voici une petite histoire Python démontrant que la toute dernière appli en date en a plus sous le capot qu'on pourrait le croire.
Et voilà le résultat (avec overclock), un peu lent dans les passages difficiles mais plus rapide que l'original la plupart du temps !
• Transférez le dossier ba dans la mémoire de stockage (avec les 44 fichiers dedans).
• Transférez demo.py à côté de ba (vous pouvez le renommer).
• Lancez demo.py, et enjoy!
La plupart des optimisations réalisées sont spécifiques à ce programme, mais j'ai trouvé au passage une bonne façon de stocker des données de façon très compacte, qui peut être réutilisée.
Version originale : noir et blanc, différences entre frames
Le but de ce programme est de faire un rendu vidéo de Bad Apple. C'est une vidéo très pratique parce que tout est en noir et blanc donc il y a peu de détails à afficher, et la plupart des pixels ne changent pas de couleur d'une image à l'autre (le fond en particulier ne change quasiment jamais).
Le programme original de Darks pour le concours de démos graphiques affiche la première image de la vidéo en taille 128x96, et ensuite contient seulement les pixels à modifier pour passer d'une image à la suivante. On gagne beaucoup de place parce que sur les ~12000 pixels la majorité ne change pas de couleur et donc on n'a pas besoin de les lister ni de les redessiner.
De plus, les pixels ne changent pas de couleurs tous seuls, souvent ils changent en groupe (quand un pixel change, la plupart du temps ses voisins changent aussi). Darks groupe donc les pixels qui changent par bandes horizontales ; c'est une optimisation bien connue qui s'appelle run-length encoding. La bande est représentée par un tuple (y,x1,x2,color) : y est la ligne où elle se trouve, x1 et x2 sont les positions horizontales du début et de la fin de la bande, et color vaut 0 si la bande est noire dans la nouvelle image, 1 si elle est blanche.
Voilà par exemple les modifications nécessaires pour passer de l'image 15 à l'image 16 :
Il y a 7 plages, entre les lignes 43 et 49, qui deviennent toutes blanches.
Pour afficher la vidéo, on commence par la première image (qui est blanche) et ensuite on affiche toutes les bandes avec cette boucle :
colors = [(0,0,0), (255,255,255)]
for (y, x1, x2, c) in frame:
for x in range(x1, x2 + 1):
set_pixel(2*x, 2*y, colors[c])
set_pixel(2*x+1, 2*y, colors[c])
set_pixel(2*x, 2*y+1, colors[c])
set_pixel(2*x+1, 2*y+1, colors[c])
show_screen()
Il y a 4 set_pixel() parce que l'image est agrandie au passage de 128x96 (la résolution de la vidéo) à 256x192 (plus proche de la taille de l'écran). Prendre la vidéo directement à 256x192 aurait été plus difficile.
Le script Python charge les images une par une depuis des fichiers Python, comme ça il peut supprimer les images de la mémoire après les avoir affichées. C'est pratique, mais du coup il y a des fichiers très petits comme celui ci-dessus et d'autres beaucoup plus gros lorsqu'on passe par exemple d'une fond blanc à un fond noir ou inversement.
À ce stade, le programme tourne à 2-3 FPS sans overclock. Clairement, on peut faire mieux ! Il y a trois pistes à explorer : rendre le code Python plus compact, rendre le format vidéo plus compact, et éviter de charger trop de fichiers.
Compacter le code avec des bytes
Ma première idée pour améliorer le format était de grouper les tuples en entiers. En effet, les valeurs sont toutes petites : y est entre 0 et 95, x1 et x2 sont entre 0 et 127, et c vaut soit 0 soit 1. On peut aisément combiner les 4 dans un entier de 32 bits, ce qui donne le résultat suivant pour le premier exemple (avec c en octet de poids fort pour gagner quelque chiffres).
Le défaut des tuples c'est qu'ils sont alloués dans le tas, donc il faut faire un malloc() chaque fois qu'on en crée un, et ça prend du temps supplémentaire qui s'accumule vite. Je pensais que les petits entiers en étaient exempts, mais les performances n'ont pas vraiment grimpé avec cette modification, donc peut-être qu'ils y passent aussi.
Cependant, l'idée de compacter ainsi est bonne, il suffit de la formuler autrement. Si un entier ne convient pas, alors un peut utiliser un bytes. Le type bytes est un tableau d'octets, si vous n'êtes pas familier avec c'est comme une liste sauf que :
• Il est de taille fixe et on ne peut pas modifier les éléments.
• Les éléments sont uniquement des entiers entre 0 et 255 (des « octets »).
• On peut les écrire comme une chaîne de caractères.
• Il est beaucoup plus léger et beaucoup plus compact qu'une liste.
Par exemple (et j'évite de rentre dans les détails), le bytes suivant contient deux éléments, 64 et 47. La partie b" au début est fixe et signifie qu'on crée un bytes, le " à la fin est fixe aussi et marque la fin de la séquence, et les deux caractères au milieu représentent un élément chacun (@ c'est 64 et / c'est 47).
b"@/"
Il y a deux avantages à ce système : d'une part il n'y a pas besoin de créer de liste, d'entiers ou de tuples, ce qui simplifie beaucoup le chargement ; et d'autre part pour chaque caractère dans le code source on a un octet de données dans le programme, ce qui parfait en termes de compacité, car c'est le maximum possible !
(Pour les curieux : il y a quelques caractères qu'il faut échapper, à savoir le backslash, les \r et \n, et le guillemet fermant. MicroPython accepte les octets nuls bruts, ce qui est vraiment important parce qu'il y en a parfois beaucoup !)
L'inconvénient de cette méthode c'est que beaucoup de valeurs entre 0 et 255 ne correspondent pas à des caractères très lisibles voire pas à des caractères du tout, donc le fichier devient illisible dans un éditeur de texte, et la calculatrice affiche des espaces partout. Ci-dessous vous pouvez voir ce à quoi ça ressemble dans vim (les parties rouges sont des caractères qui existent comme @ et /, pour les parties en bleu aucun caractère ne correspond donc vim improvise dans une autre couleur pour indiquer que c'est le bordel).
Bref, ces fichiers-là on les génère avec un programme, on les copie sur la calculatrice et on les ouvre jamais !
Compacter le format de la vidéo
Une autre amélioration que j'ai apportée au programme est de changer le format de la vidéo. Chaque image est représentée comme une liste de bandes horizontales qui doivent changer de couleur pour passer de l'image précédente à l'image actuelle. Mais dans l'ancien système avec quatre valeurs y, x1, x2 et color, il y a beaucoup de répétition :
• D'une part il y a souvent plusieurs bandes sur la même ligne, donc en moyenne le même y est recopié 4 fois sur 4 bandes successives ;
• D'autre part color ne peut valoir que 0 ou 1, lui donner un octet entier (qui peut représenter 8 fois plus d'information que ça) c'est du gâchis d'espace.
Je ne vais pas rentrer dans les détails ici, mais j'ai modifié le format pour que chaque bande soit encodée avec deux octets seulement : d'abord la valeur de x1, et ensuite une combinaison entre la valeur de x2 et celle de color. Pour la valeur de y, on commence sur la ligne 0 au début de l'image, et chaque fois qu'une bande est sur une nouvelle ligne j'ai un octet spécial qui indique de combien il faut descendre.
Ensemble, ces deux optimisations réduisent l'espace occupé par chaque bande de 4 octets à environ 2.25 en moyenne. Ce qui est super, parce que moins de données à manipuler ça veut dire que le chargement est beaucoup plus rapide, et souvent le code aussi.
Améliorer le chargement des fichiers
Initialement on avait un fichier Python par image, et Darks avait extrait 1000 images de la vidéo (la moitié environ). Ça fait beaucoup, surtout que sur les 1000 images certaines sont presque identiques aux précédentes, ce qui donne des fichiers quasi-vides et donc des import quasi-inutiles.
Darks avait programmé une option dans sa démo initiale pour mettre plusieurs images dans un seul fichier, et quand je l'ai testée j'ai tout de suite remarqué que c'était crucial : avec 3 images par fichier, on a un enchaînement fluide de 3 images, une petite saccade le temps de charger le fichier suivant, de nouveau 3 images fluides, une petite saccade...
Il est clair que la plupart du temps est passé à charger les fichiers puis à créer les variables listes ou bytes qui contiennent les séquences de bandes. C'est pour ça que compacter est si important : réduire la taille du fichier accélère la première partie, et éliminer des tuples et des listes accélère la seconde.
En plus, le fichier principal (demo.py) peut être très long s'il doit importer 1000 fichiers différents, donc plus on groupe d'images dans les mêmes sous-fichiers, plus demo.py est court, plus le chargement initial est rapide. C'est gagant-gagnant-gagnant !
Pour profiter au maximum de cette possibilité, j'ai modifié le convertisseur qui génère les données à partir de la vidéo pour mettre autant d'images possible dans chaque fichier, jusqu'à atteindre une taille choisie à l'avance (10 kio). Ça veut dire que dans les parties où les images ne changent pas beaucoup je peux mettre beaucoup d'images dans le même fichier, et dans les parties où les images changent beaucoup je garde des fichiers assez petits pour ne pas saturer la mémoire l'appli Python.
Les modifications que j'ai présentées ci-dessus réduisent la taille totale du projet de 2587 kio à 463 kio (soit 5 fois plus petit environ), et demo.py de 42 kio à juste 2 kio. Il y avait 1000 fichiers au début pour stocker toutes les images, et seulement 44 maintenant grâce au groupement. Et cerise sur le gâteau, c'est beaucoup plus rapide !
Conclusion
Malgré les limitations qui lui sont propres, Python dépasse le Basic CASIO de loin sur plusieurs aspects. Le module de dessin casioplot, bien plus flexible (et performant) que les alternatives en Basic, nous montre bien que le langage et l'interpréteur offrent des possibilités tout à fait inédites et jusqu'ici seulement accessibles aux add-ins.
Il faut bien sûr un grain de folie pour utiliser des bytes comme ça, mais c'est loin d'être la technique la plus extravagante utilisée couramment sur Planète Casio. Je pense qu'avec le temps d'autres astuces vont apparaître et rendre le Python de plus en plus attractif!
N'hésitez pas à demander des clarifications en commentaires, ou à proposer d'autres idées pour des projets fous en Python.
Est ce qu'il y a besoin de préciser la qualité d'un article de Lephe ?
En vrai, c'est un super article, même si je n'ai pas compris tous les détails de la partie "Compacter le code avec des bytes" x) (note à moi même : revoir ton TDM sur les données ou sur la mémoire, je dois voir lequel correspond).
Ça pourrait limite être un TDM comme exemple, mais vu qu'on est jeudi, c'est pas possible
Merci ! Pour l'histoire des bytes c'est un vraiment le sujet couvert dans le TDM oui. Ultimement, un bytes c'est vraiment une séquence d'octets sous sa forme la plus pure. Ce type incarne la notion de « données libres » parfaitement, car tu peux y mettre ce que tu veux au bit près.
Ensuite tu arrives avec toute la partie « chaîne de caractère » qui est moins intuitive. Si tu veux avoir les trois octets 35, 87 et 73, tu peux écrire bytes([ 35, 87, 73 ]), mais ça prend beaucoup de texte et le fichier Python est gros. C'est là que le texte aide : cette séquence de trois octets sert à représenter le texte "#WI" en encodage ASCII (ou UTF-8 ici), et pour te simplifier la vie Python te laisse écrire ces trois caractères dans le code source (entre b" et ") et il récupère les octets associés. C'est plus court !
Tant que la séquence que tu veux correspond à du texte ASCII ou UTF-8, tu peux faire ça. Maintenant y'a plein d'octets que tu ne « peux pas » obtenir en ASCII ou UTF-8, par exemple 129, donc il n'y a pas de caractère que tu peux mettre entre b"" pour avoir l'octet 129 dans la séquence. Mais comme je suis têtu, je mets quand même un octet 129 dans le fichier source Python entre le b" et le ". Ça fait de mon fichier Python un fichier texte invalide et du coup il ne ressemble à rien dans vim, mais MicroPython ne s'en soucie pas trop et il accepte l'octet quand même. C'est un peu osé mais c'est super efficace !
Pas mal ! Du coup RLE 2 couleurs c'est ce que j'ai fait comme format (enfin Darks plus précisément) et j'ai 1m41s pour les 1000 frames, couvrant 463 kio. Si on extrapole un peu, on peut s'attendre à ce que la vidéo complète tienne en moins d'1 Mo en 128x96.
256x256 ce serait stylé pour un add-in. 16 Mo c'est pas mal déjà mais ça tient pas encore dans la mémoire de stockage, est-ce qu'il te reste des pistes sur le format ou toute la différence est liée à la plus grande résolution ?
je voulais dire que cette version est démunie de RLE et elle est en 2 couleurs
la version en haut est en RLE avec 256 couleurs
Ce que je pourrais faire pour optimiser c'est de mettre du RLE pas que pour les pixels d'une frame, mais pour les frames aussi, mais bon, c'est trop pour que mon cerveau comprenne.
Ah, je vois c'est plus clair. Effectivement en 256 couleurs inutile de faire du RLE... j'ai toujours pensé que pour bien compresser avec beaucoup de couleurs il fallait regarder du côté de vrais codecs vidéos (genre les simples), mais j'ai jamais vraiment cherché en détail et je sais pas si on a assez de puissance de calcul pour décoder en temps réel.
il fallait regarder du côté de vrais codecs vidéos (genre les simples)
J'avais commencé à regarder, le plus simple selon moi est le M-JPEG. En gros c'est une succession de Jpeg les uns derrière les autres (pour faire simple).
Le problème est que quelque soit le codec que tu implémente, tu te retrouve avec un code assez… compliqué. Je comprends ce que tu disais quand les HID vidéo étaient difficiles à appréhender, je pense que ça vient aussi du fait que la vidéo est quelque chose de non-trivial.
Niveau performances faut voir, mais je pense qu'encore une fois ce qui risque de limiter, c'est la flash.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Hmm le JPG c'est pas évident à cause de la transformation en cosinus discrète, qui demande pas mal de calcul en plus d'avoir du point fixe/flottant. C'est pas impossible avec des tables mais vu qu'il y a, pour chaque bloc de 8x8 pixels, une double somme (8x8 = 64 termes) de produits de cosinus pour chacun des 64 pixels, tu te retrouves avec 128 facteurs de la forme cos((2x+1)uπ/16) à calculer par pixel, et il devient évident pourquoi le SH7724 a un module périphérique qui fait ça à ta place.
Hmm, j'ai pensé a une methode de compression(bon elle est a perte, mais bon)
1: Créer des "blocks" et leur donner un ID(ces blocks ne contiennent pas de couleur, juste des indexs)
2: On regarde tout les blocks de pixels(de la meme taille que les block d'index), un à un et on se pose la question: "Quel block d'index est le plus proche de ce block de pixel?"
3: On met l'id du block d'index le plus proche dans le fichier, et on met une approximation de toutes les couleurs dans le block de pixels juste apres(voila pourquoi il y a des indexs dans les blocks)
Enfin c'est la premiere idée que j'ai eu en tete après avoir abandonné le RLE pour le mode 256 couleurs.
En gros une palette de blocs. C'est pas stupide... je pense qu'on peut calculer un peu pour se donner une idée de si ça va bien marcher.
Clairement une palette de 256 blocs c'est trop petit pour du 256 couleurs. Si tu veux prendre plus, l'option naturelle suivante c'est soit 4096 soit 65536 blocs. Le second est tentant, le truc c'est qu'il faudrait mettre au moins 3 pixels dedans sinon l'index prend autant de place que les valeurs, et 3×64k ça ne rentrerait pas dans la mémoire de travail en Python, et serait aussi très gros à charger en C.
Imaginons qu'on fasse des blocs de 2×2 pour voir. La distance avec laquelle on va chercher le « plus proche » n'est pas n'importe laquelle. Après tout, on peut se permettre des approximations sur la couleur des pixels mais on peut pas trop se permettre d'avoir les couleurs dans le mauvais ordre. Si on part dans le cas simple où la distance c'est une combinaison des distances sur chaque pixel individuel du bloc, la compression reviendra au même que pré-discrétiser la vidéo, et on gagne juste le stockage des blocs ; ce qui peut être pas mal déjà, d'autant plus que coder à la main un algo pour trouver une bonne palette c'est pas facile.
Sur du 2×2, en 256 couleurs tu représentes 4 octets de données par entrée de la palette. Mais quand on y réfléchit, même une vidéo de 192×192 n'a que 9216 blocs de cette taille par image (96²), ce que tient dans 16 (14) bits. Donc même sans compression, tu passes de 192²×2 = 74 kio de données brutes à 96²×2 indices de blocs + 96²×4 contenus de blocs = 55 kio.
Tu peux d'ailleurs faire des blocs de plus en plus gros et ce motif converge.
With blocs of size 2x2:
Blocks: 9216
Bytes per index: 2
Bytes per definition: 4
Total size: 55296
With blocs of size 3x3:
Blocks: 4096
Bytes per index: 2
Bytes per definition: 9
Total size: 45056
With blocs of size 4x4:
Blocks: 2304
Bytes per index: 2
Bytes per definition: 16
Total size: 41472
With blocs of size 6x6:
Blocks: 1024
Bytes per index: 2
Bytes per definition: 36
Total size: 38912
With blocs of size 8x8:
Blocks: 576
Bytes per index: 2
Bytes per definition: 64
Total size: 38016
With blocs of size 12x12:
Blocks: 256
Bytes per index: 1
Bytes per definition: 144
Total size: 37120
With blocs of size 16x16:
Blocks: 144
Bytes per index: 1
Bytes per definition: 256
Total size: 37008
Mais maintenant ce qui est intéressant c'est de prendre les 9216 blocs et d'en supprimer. Une fois éliminé les tous noirs et tous blancs qui méritent 100% un encodage spécial à 1 octet voire du RLE, un petit coup de clustering type k-medians paraît approprié ici pour réduire le nombre de blocs différents sans détruire l'aspect visuel. Il est peu probable de passer sous 256 blocs, mais passer sous 4096 devrait être totalement faisable, ce qui laisserait 96²×1.5 octets d'indices + 4096×4 octets de couleurs = 30 kio de données par frame. On est déjà sous la limite du système sans compression même avec les gros blocs, et encore j'ai pas compté l'optimisation des blocs tous noirs ou tous blancs.
Après on reste relativement loin du format mono RLE (qui fait tenir un frame en 463 octets en moyenne dans mon cas), mais ça pourrait déjà être pas mal.
Sinon, au lieu de s'emmerder avec les blocs tous noirs ou tous blancs, tu passes juste un coup de Huffman ou de DEFLATE sur le résultat et ça compressera automatiquement tous ces blocs qui se répètent. Le décodage ne serait pas un problème en C, mais en Python c'est une autre affaire c'est sûr.
Note que tout ça ressemble un peu à JPEG; la différence est quand le format JPEG on décrit le blocs comme une combinaisons de motifs prédéfinis (à base de transformée en cosinus discrète) et ensuite on supprime l'information concernant les motifs moins visibles pour l'oeil humain.
Salut !
J'ai regardé ce topic pour voir le fonctionnement de la compression de données et j'ai tenté de le reproduire, mais je ne suis pas parvenu car je ne comprend pas comment t'as réussi à transformer un .py en byte et qui en plus il peut être importé.
Je tente de refaire avec mon script.
J'aimerai bien comprendre comment tu as fait ça.
Merci d'avance
"La créativité est contagieuse faites la tourner" Albert Einstein
Un bytes() c'est une liste d'octets, et un octet c'est un petit entier dont la valeur peut aller entre 0 et 255. La première chose à faire c'est donc de modifier ton programme pour utiliser une liste « plate » :
Créer ton bytes() comme ça n'économise pas vraiment de mémoire parce que tu dois quand même créer la liste avant de créer le bytes. Par contre, ça te donne le temps de modifier tout le reste de ton code pour vérifier que (1) tu n'écris pas dedans et (2) il n'y a pas de valeur plus grande que 255. Là tu peux debugger jusqu'à ce que ça marche.
Tu noteras qu'on ne peut pas écrire dans un bytes(). Python est conçu comme ça. Normalement si tu veux écrire dedans tu peux juste faire un bytearray(), qui est exactement pareil à part ce droit d'écriture. Mais, sur la calculatrice, ce type n'existe pas ! Encore une tragédie...
Une fois que tu as fait ça, tu peux commencer à écrire ton bytes() de plus en plus court. À partir de cette étape on rentre dans un territoire où la modification du fichier est très ingrate, et je te conseille fortement de le générer automatiquement. (Mais vu la taille de ta tilesheet c'est déjà ce que tu fais ha ha !)
La syntaxe d'un bytes(), pour des raisons pas importantes ici, c'est une chaîne de caractères avec le préfixe b. Chaque valeur est représentée par une lettre (et la valeur est le code ASCII de la lettre) ou bien le code \xNN où NN est une valeur en hexadécimal. Par exemple b"A" c'est pareil que bytes([65]) (65 étant le code ASCII de A) et b"\xff" c'est pareil que bytes([255]) (ff étant l'écriture hexadécimale de 255).
Là tu as gagné de la mémoire parce que ton programme ne construit plus la liste, par contre c'est illisible est le code est encore un peu long.
Pour l'étape suivante, tu peux donc compresser tout ça. Comme je l'ai mentionné, il est possible d'écrire b"A" pour avoir la valeur 65. Si tu fais ça, dans ton fichier tu auras littéralement un octet de valeur 65 entre les deux guillemets. Ça veut dire que la valeur 65 prendra dans ton fichier un seul octet (la lettre A) au lieu de 4 octets (la séquence \x41 qui représente 65 en hexadécimal). C'est important parce que la calculatrice charge le code dans la mémoire avant de l'exécuter, et 4 fois moins de code = 4 fois plus de place pour faire autre chose. Dans ton générateur, c'est donc important d'écrire les valeurs comme des lettres ou des caractères lisibles quand c'est possible.
Tu peux voir dans l'image ci-dessous qu'il y a plein de caractères qui sont écrits verbatim (en rouge).
Mais on ne s'arrête pas là. En effet, quand Python lit ton fichier, il prend les octets qu'il voit entre les guillemets, remplace les séquences d'échappement comme \xNN ou \n, et garde le reste intact. Qu'est-ce qui nous empêche donc de mettre un octet de valeur 129 ou 255 ou autre valeur qui ne représente aucun caractère entre les guillemets ?
Eh bien, rien en fait. Sur l'image ci-dessus, tu vois les <81> en bleu ? C'est des octets de valeur 0x81 = 129 entre les guillemets. Ces octets ne représentent aucun caractère, donc l'éditeur de texte (vim) les affiche en bleu pour me signaler leur présence. MicroPython les accepte, et ils ont le même effet que \x81 sauf qu'ils prennent 4 fois moins de place (un seul octet de valeur 129 dans le fichier au lieu de 4 octets pour la séquence de 4 caractères \x81).
Il faut faire attention à quelques cas cela dit. On ne peut pas mettre n'importe quoi entre des guillemets en Python.
D'abord tu ne peux pas mettre un guillemet fermant (octet de valeur 34), sinon la chaîne s'arrête. À la place, tu dois l'échapper avec un backslash en écrivant \" (série de deux octets : 92, 34, sachant que 92 est le backslash). Ensuite tu ne peux pas mettre un backslash tout seul, tu dois l'échapper aussi en écrivant \\ (donc la valeur 92 est remplacée par la série de deux octets : 92, 92). Il en va de même pour les valeurs 13 (retour chariot) et 10 (fin de ligne), qu'il faut remplacer par les séquences \r (92, 114) et \n (92, 110).
Enfin la valeur 0, représentée usuellement par la séquence \x00 (parce que 0 n'est associé à aucun caractère lisible en ASCII), est un peu spéciale. Il est également possible de mettre un octet de valeur nulle (= 0) entre des guillemets dans ton fichier, par contre (1) sur l'ordinateur, Python donnera une erreur de syntaxe, (2) il faut le générer avec un programme parce que ton éditeur de texte ne te permet probablement pas de l'insérer. De préférence il ne faut jamais modifier le fichier généré, donc il vaut mieux le cacher dans un import (comme on fait dans Bad Apple). Perso je conseille de faire cette optimisation, parce que le fichier est illisible de toute façon, tant que la compatibilité PC n'est pas un must. En général il y a beaucoup de 0 dans les données et on n'a vraiment pas envie de dépenser 4 octets pour écrire la séquence \x00 quand on peut mettre un véritable octet nul dans le fichier.
Je te laisse avec le code Python de la conversion pour Bad Apple. Dans ce code, fp est un fichier ouvert et data contient une liste de tuples (y, x1, x2, color). Je te laisse voir la fonction byteify() qui implémente les quelques règles dont j'ai parlé à l'instant. La boucle contient du code assez spécifique à Bad Apple mais tu peux voir que j'écris une valeur entière à chaque fp.write(byteify(...)), en suivant le format que j'avais choisi pour ce programme.
# Compact into byte strings to avoid building tuples in the heap;
# MicroPython allows basically anything in literal strings (including
# NUL!), we just have to escape \, \n, \r, and ".
def byteify(c):
if c == ord('"'):
return b'\\"'
if c == ord('\n'):
return b'\\n'
if c == ord('\r'):
return b'\\r'
if c == ord('\\'):
return b'\\\\'
return bytes([c])
fp.write(b'b"')
previous_y = 0
written_length = 0
for (y, x1, x2, color) in data:
global max_dx, max_dy, y_changes, runs
max_dx = max(max_dx, x2 - x1)
max_dy = max(max_dy, y - previous_y)
# If y changes, write the change
if y != previous_y:
fp.write(byteify(0x80 + (y - previous_y)))
written_length += 1
# Write the run
fp.write(byteify(x1))
fp.write(byteify((color << 7) | x2))
written_length += 2
# Approximate number of bytes written to file
return written_length
Je terminerai ce message avec le plus important : commence par encoder tes données dans un format qui convient mieux. Ta liste semble avoir beaucoup, beaucoup de répétition de [255, 255, 255, 0] ou de [0, 0, 0, 128]. Commence par créer une palette/un index de ces valeurs si tu n'as pas beaucoup de possibilités, ou utilise un encodage à longueur variable. Tu diviseras déjà la quantité de données par 2, 3 ou 4 avant même d'avoir à réfléchir à si tu la mets dans des listes ou des bytes().
Au passage, rien que les espaces après tes virgules sont superflus là. Le texte "[255, 255, 255, 0], " prend 20 octets alors que tu peux l'écrire sur 4 octets avec la méthode des bytes(), et probablement 2 octets avec une palette. Autrement dit tu peux probablement diviser la taille de ton fichier Python par 5 ou 10 avec un peu d'effort.
Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd
Citer : Posté le 15/04/2021 18:18 | #
Est ce qu'il y a besoin de préciser la qualité d'un article de Lephe ?
En vrai, c'est un super article, même si je n'ai pas compris tous les détails de la partie "Compacter le code avec des bytes" x) (note à moi même : revoir ton TDM sur les données ou sur la mémoire, je dois voir lequel correspond).
Ça pourrait limite être un TDM comme exemple, mais vu qu'on est jeudi, c'est pas possible
Citer : Posté le 15/04/2021 19:19 | #
Merci ! Pour l'histoire des bytes c'est un vraiment le sujet couvert dans le TDM oui. Ultimement, un bytes c'est vraiment une séquence d'octets sous sa forme la plus pure. Ce type incarne la notion de « données libres » parfaitement, car tu peux y mettre ce que tu veux au bit près.
Ensuite tu arrives avec toute la partie « chaîne de caractère » qui est moins intuitive. Si tu veux avoir les trois octets 35, 87 et 73, tu peux écrire bytes([ 35, 87, 73 ]), mais ça prend beaucoup de texte et le fichier Python est gros. C'est là que le texte aide : cette séquence de trois octets sert à représenter le texte "#WI" en encodage ASCII (ou UTF-8 ici), et pour te simplifier la vie Python te laisse écrire ces trois caractères dans le code source (entre b" et ") et il récupère les octets associés. C'est plus court !
Tant que la séquence que tu veux correspond à du texte ASCII ou UTF-8, tu peux faire ça. Maintenant y'a plein d'octets que tu ne « peux pas » obtenir en ASCII ou UTF-8, par exemple 129, donc il n'y a pas de caractère que tu peux mettre entre b"" pour avoir l'octet 129 dans la séquence. Mais comme je suis têtu, je mets quand même un octet 129 dans le fichier source Python entre le b" et le ". Ça fait de mon fichier Python un fichier texte invalide et du coup il ne ressemble à rien dans vim, mais MicroPython ne s'en soucie pas trop et il accepte l'octet quand même. C'est un peu osé mais c'est super efficace !
Citer : Posté le 15/04/2021 19:22 | #
D'accord, je vois, c'est super clair !
Je vais quand même finir de revoir le TDM, ça sera sans aucun doute utile
Citer : Posté le 18/04/2021 10:19 | #
on avance petit a petit(en 256*256 avec RLE en haut et meme resolution, sans RLE 2 couleurs en bas
Citer : Posté le 18/04/2021 11:15 | #
Pas mal ! Du coup RLE 2 couleurs c'est ce que j'ai fait comme format (enfin Darks plus précisément) et j'ai 1m41s pour les 1000 frames, couvrant 463 kio. Si on extrapole un peu, on peut s'attendre à ce que la vidéo complète tienne en moins d'1 Mo en 128x96.
256x256 ce serait stylé pour un add-in. 16 Mo c'est pas mal déjà mais ça tient pas encore dans la mémoire de stockage, est-ce qu'il te reste des pistes sur le format ou toute la différence est liée à la plus grande résolution ?
(J'ai corrigé tes liens.)
Citer : Posté le 18/04/2021 13:50 | #
Alors, quand je disais
sans RLE 2 couleurs en bas
je voulais dire que cette version est démunie de RLE et elle est en 2 couleurs
la version en haut est en RLE avec 256 couleurs
Ce que je pourrais faire pour optimiser c'est de mettre du RLE pas que pour les pixels d'une frame, mais pour les frames aussi, mais bon, c'est trop pour que mon cerveau comprenne.
Citer : Posté le 18/04/2021 19:08 | #
Ah, je vois c'est plus clair. Effectivement en 256 couleurs inutile de faire du RLE... j'ai toujours pensé que pour bien compresser avec beaucoup de couleurs il fallait regarder du côté de vrais codecs vidéos (genre les simples), mais j'ai jamais vraiment cherché en détail et je sais pas si on a assez de puissance de calcul pour décoder en temps réel.
Citer : Posté le 18/04/2021 20:44 | #
J'avais commencé à regarder, le plus simple selon moi est le M-JPEG. En gros c'est une succession de Jpeg les uns derrière les autres (pour faire simple).
Le problème est que quelque soit le codec que tu implémente, tu te retrouve avec un code assez… compliqué. Je comprends ce que tu disais quand les HID vidéo étaient difficiles à appréhender, je pense que ça vient aussi du fait que la vidéo est quelque chose de non-trivial.
Niveau performances faut voir, mais je pense qu'encore une fois ce qui risque de limiter, c'est la flash.
Citer : Posté le 18/04/2021 23:02 | #
Hmm le JPG c'est pas évident à cause de la transformation en cosinus discrète, qui demande pas mal de calcul en plus d'avoir du point fixe/flottant. C'est pas impossible avec des tables mais vu qu'il y a, pour chaque bloc de 8x8 pixels, une double somme (8x8 = 64 termes) de produits de cosinus pour chacun des 64 pixels, tu te retrouves avec 128 facteurs de la forme cos((2x+1)uπ/16) à calculer par pixel, et il devient évident pourquoi le SH7724 a un module périphérique qui fait ça à ta place.
Citer : Posté le 24/04/2021 14:40 | #
Hmm, j'ai pensé a une methode de compression(bon elle est a perte, mais bon)
1: Créer des "blocks" et leur donner un ID(ces blocks ne contiennent pas de couleur, juste des indexs)
2: On regarde tout les blocks de pixels(de la meme taille que les block d'index), un à un et on se pose la question: "Quel block d'index est le plus proche de ce block de pixel?"
3: On met l'id du block d'index le plus proche dans le fichier, et on met une approximation de toutes les couleurs dans le block de pixels juste apres(voila pourquoi il y a des indexs dans les blocks)
Enfin c'est la premiere idée que j'ai eu en tete après avoir abandonné le RLE pour le mode 256 couleurs.
Citer : Posté le 24/04/2021 15:08 | #
En gros une palette de blocs. C'est pas stupide... je pense qu'on peut calculer un peu pour se donner une idée de si ça va bien marcher.
Clairement une palette de 256 blocs c'est trop petit pour du 256 couleurs. Si tu veux prendre plus, l'option naturelle suivante c'est soit 4096 soit 65536 blocs. Le second est tentant, le truc c'est qu'il faudrait mettre au moins 3 pixels dedans sinon l'index prend autant de place que les valeurs, et 3×64k ça ne rentrerait pas dans la mémoire de travail en Python, et serait aussi très gros à charger en C.
Imaginons qu'on fasse des blocs de 2×2 pour voir. La distance avec laquelle on va chercher le « plus proche » n'est pas n'importe laquelle. Après tout, on peut se permettre des approximations sur la couleur des pixels mais on peut pas trop se permettre d'avoir les couleurs dans le mauvais ordre. Si on part dans le cas simple où la distance c'est une combinaison des distances sur chaque pixel individuel du bloc, la compression reviendra au même que pré-discrétiser la vidéo, et on gagne juste le stockage des blocs ; ce qui peut être pas mal déjà, d'autant plus que coder à la main un algo pour trouver une bonne palette c'est pas facile.
Sur du 2×2, en 256 couleurs tu représentes 4 octets de données par entrée de la palette. Mais quand on y réfléchit, même une vidéo de 192×192 n'a que 9216 blocs de cette taille par image (96²), ce que tient dans 16 (14) bits. Donc même sans compression, tu passes de 192²×2 = 74 kio de données brutes à 96²×2 indices de blocs + 96²×4 contenus de blocs = 55 kio.
Tu peux d'ailleurs faire des blocs de plus en plus gros et ce motif converge.
Blocks: 9216
Bytes per index: 2
Bytes per definition: 4
Total size: 55296
With blocs of size 3x3:
Blocks: 4096
Bytes per index: 2
Bytes per definition: 9
Total size: 45056
With blocs of size 4x4:
Blocks: 2304
Bytes per index: 2
Bytes per definition: 16
Total size: 41472
With blocs of size 6x6:
Blocks: 1024
Bytes per index: 2
Bytes per definition: 36
Total size: 38912
With blocs of size 8x8:
Blocks: 576
Bytes per index: 2
Bytes per definition: 64
Total size: 38016
With blocs of size 12x12:
Blocks: 256
Bytes per index: 1
Bytes per definition: 144
Total size: 37120
With blocs of size 16x16:
Blocks: 144
Bytes per index: 1
Bytes per definition: 256
Total size: 37008
Mais maintenant ce qui est intéressant c'est de prendre les 9216 blocs et d'en supprimer. Une fois éliminé les tous noirs et tous blancs qui méritent 100% un encodage spécial à 1 octet voire du RLE, un petit coup de clustering type k-medians paraît approprié ici pour réduire le nombre de blocs différents sans détruire l'aspect visuel. Il est peu probable de passer sous 256 blocs, mais passer sous 4096 devrait être totalement faisable, ce qui laisserait 96²×1.5 octets d'indices + 4096×4 octets de couleurs = 30 kio de données par frame. On est déjà sous la limite du système sans compression même avec les gros blocs, et encore j'ai pas compté l'optimisation des blocs tous noirs ou tous blancs.
Après on reste relativement loin du format mono RLE (qui fait tenir un frame en 463 octets en moyenne dans mon cas), mais ça pourrait déjà être pas mal.
Sinon, au lieu de s'emmerder avec les blocs tous noirs ou tous blancs, tu passes juste un coup de Huffman ou de DEFLATE sur le résultat et ça compressera automatiquement tous ces blocs qui se répètent. Le décodage ne serait pas un problème en C, mais en Python c'est une autre affaire c'est sûr.
Note que tout ça ressemble un peu à JPEG; la différence est quand le format JPEG on décrit le blocs comme une combinaisons de motifs prédéfinis (à base de transformée en cosinus discrète) et ensuite on supprime l'information concernant les motifs moins visibles pour l'oeil humain.
Citer : Posté le 12/09/2021 14:04 | #
Salut !
J'ai regardé ce topic pour voir le fonctionnement de la compression de données et j'ai tenté de le reproduire, mais je ne suis pas parvenu car je ne comprend pas comment t'as réussi à transformer un .py en byte et qui en plus il peut être importé.
Je tente de refaire avec mon script.
J'aimerai bien comprendre comment tu as fait ça.
Merci d'avance
Albert Einstein
Citer : Posté le 12/09/2021 21:28 | #
C'est une excellente question !
La première étape est de changer ta liste en bytes sans tricher sur la syntaxe. Mettons que ta liste c'est ça (j'ai supprimé un niveau de liste) :
Un bytes() c'est une liste d'octets, et un octet c'est un petit entier dont la valeur peut aller entre 0 et 255. La première chose à faire c'est donc de modifier ton programme pour utiliser une liste « plate » :
# Tilesheet_B[i][j] devient Tilesheet_B[4*i+j]
Après avoir modifié ton code le programme marche toujous. Tu peux ensuite créer un véritable bytes() en convertissant la liste :
Créer ton bytes() comme ça n'économise pas vraiment de mémoire parce que tu dois quand même créer la liste avant de créer le bytes. Par contre, ça te donne le temps de modifier tout le reste de ton code pour vérifier que (1) tu n'écris pas dedans et (2) il n'y a pas de valeur plus grande que 255. Là tu peux debugger jusqu'à ce que ça marche.
Tu noteras qu'on ne peut pas écrire dans un bytes(). Python est conçu comme ça. Normalement si tu veux écrire dedans tu peux juste faire un bytearray(), qui est exactement pareil à part ce droit d'écriture. Mais, sur la calculatrice, ce type n'existe pas ! Encore une tragédie...
Une fois que tu as fait ça, tu peux commencer à écrire ton bytes() de plus en plus court. À partir de cette étape on rentre dans un territoire où la modification du fichier est très ingrate, et je te conseille fortement de le générer automatiquement. (Mais vu la taille de ta tilesheet c'est déjà ce que tu fais ha ha !)
La syntaxe d'un bytes(), pour des raisons pas importantes ici, c'est une chaîne de caractères avec le préfixe b. Chaque valeur est représentée par une lettre (et la valeur est le code ASCII de la lettre) ou bien le code \xNN où NN est une valeur en hexadécimal. Par exemple b"A" c'est pareil que bytes([65]) (65 étant le code ASCII de A) et b"\xff" c'est pareil que bytes([255]) (ff étant l'écriture hexadécimale de 255).
Là tu as gagné de la mémoire parce que ton programme ne construit plus la liste, par contre c'est illisible est le code est encore un peu long.
Pour l'étape suivante, tu peux donc compresser tout ça. Comme je l'ai mentionné, il est possible d'écrire b"A" pour avoir la valeur 65. Si tu fais ça, dans ton fichier tu auras littéralement un octet de valeur 65 entre les deux guillemets. Ça veut dire que la valeur 65 prendra dans ton fichier un seul octet (la lettre A) au lieu de 4 octets (la séquence \x41 qui représente 65 en hexadécimal). C'est important parce que la calculatrice charge le code dans la mémoire avant de l'exécuter, et 4 fois moins de code = 4 fois plus de place pour faire autre chose. Dans ton générateur, c'est donc important d'écrire les valeurs comme des lettres ou des caractères lisibles quand c'est possible.
Tu peux voir dans l'image ci-dessous qu'il y a plein de caractères qui sont écrits verbatim (en rouge).
Mais on ne s'arrête pas là. En effet, quand Python lit ton fichier, il prend les octets qu'il voit entre les guillemets, remplace les séquences d'échappement comme \xNN ou \n, et garde le reste intact. Qu'est-ce qui nous empêche donc de mettre un octet de valeur 129 ou 255 ou autre valeur qui ne représente aucun caractère entre les guillemets ?
Eh bien, rien en fait. Sur l'image ci-dessus, tu vois les <81> en bleu ? C'est des octets de valeur 0x81 = 129 entre les guillemets. Ces octets ne représentent aucun caractère, donc l'éditeur de texte (vim) les affiche en bleu pour me signaler leur présence. MicroPython les accepte, et ils ont le même effet que \x81 sauf qu'ils prennent 4 fois moins de place (un seul octet de valeur 129 dans le fichier au lieu de 4 octets pour la séquence de 4 caractères \x81).
Il faut faire attention à quelques cas cela dit. On ne peut pas mettre n'importe quoi entre des guillemets en Python.
D'abord tu ne peux pas mettre un guillemet fermant (octet de valeur 34), sinon la chaîne s'arrête. À la place, tu dois l'échapper avec un backslash en écrivant \" (série de deux octets : 92, 34, sachant que 92 est le backslash). Ensuite tu ne peux pas mettre un backslash tout seul, tu dois l'échapper aussi en écrivant \\ (donc la valeur 92 est remplacée par la série de deux octets : 92, 92). Il en va de même pour les valeurs 13 (retour chariot) et 10 (fin de ligne), qu'il faut remplacer par les séquences \r (92, 114) et \n (92, 110).
Enfin la valeur 0, représentée usuellement par la séquence \x00 (parce que 0 n'est associé à aucun caractère lisible en ASCII), est un peu spéciale. Il est également possible de mettre un octet de valeur nulle (= 0) entre des guillemets dans ton fichier, par contre (1) sur l'ordinateur, Python donnera une erreur de syntaxe, (2) il faut le générer avec un programme parce que ton éditeur de texte ne te permet probablement pas de l'insérer. De préférence il ne faut jamais modifier le fichier généré, donc il vaut mieux le cacher dans un import (comme on fait dans Bad Apple). Perso je conseille de faire cette optimisation, parce que le fichier est illisible de toute façon, tant que la compatibilité PC n'est pas un must. En général il y a beaucoup de 0 dans les données et on n'a vraiment pas envie de dépenser 4 octets pour écrire la séquence \x00 quand on peut mettre un véritable octet nul dans le fichier.
Je te laisse avec le code Python de la conversion pour Bad Apple. Dans ce code, fp est un fichier ouvert et data contient une liste de tuples (y, x1, x2, color). Je te laisse voir la fonction byteify() qui implémente les quelques règles dont j'ai parlé à l'instant. La boucle contient du code assez spécifique à Bad Apple mais tu peux voir que j'écris une valeur entière à chaque fp.write(byteify(...)), en suivant le format que j'avais choisi pour ce programme.
# MicroPython allows basically anything in literal strings (including
# NUL!), we just have to escape \, \n, \r, and ".
def byteify(c):
if c == ord('"'):
return b'\\"'
if c == ord('\n'):
return b'\\n'
if c == ord('\r'):
return b'\\r'
if c == ord('\\'):
return b'\\\\'
return bytes([c])
fp.write(b'b"')
previous_y = 0
written_length = 0
for (y, x1, x2, color) in data:
global max_dx, max_dy, y_changes, runs
max_dx = max(max_dx, x2 - x1)
max_dy = max(max_dy, y - previous_y)
# If y changes, write the change
if y != previous_y:
fp.write(byteify(0x80 + (y - previous_y)))
written_length += 1
# Write the run
fp.write(byteify(x1))
fp.write(byteify((color << 7) | x2))
written_length += 2
y_changes += (previous_y != y)
previous_y = y
runs += 1
fp.write(b'"')
# Approximate number of bytes written to file
return written_length
Je terminerai ce message avec le plus important : commence par encoder tes données dans un format qui convient mieux. Ta liste semble avoir beaucoup, beaucoup de répétition de [255, 255, 255, 0] ou de [0, 0, 0, 128]. Commence par créer une palette/un index de ces valeurs si tu n'as pas beaucoup de possibilités, ou utilise un encodage à longueur variable. Tu diviseras déjà la quantité de données par 2, 3 ou 4 avant même d'avoir à réfléchir à si tu la mets dans des listes ou des bytes().
Au passage, rien que les espaces après tes virgules sont superflus là. Le texte "[255, 255, 255, 0], " prend 20 octets alors que tu peux l'écrire sur 4 octets avec la méthode des bytes(), et probablement 2 octets avec une palette. Autrement dit tu peux probablement diviser la taille de ton fichier Python par 5 ou 10 avec un peu d'effort.
Citer : Posté le 13/09/2021 18:59 | #
Ok merci pour les explications, je vais optimiser un peu tout ça
Albert Einstein