Compression / Decompression de datas

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Le 28/11/2021 à 22h19

Salut Guillaume

Pour faire suite à nos échanges, voici ce, à quoi j'avais pensé (ce n'est qu'une hypothèse de recherche, tous les cas ne sont pas 'testés'). Le ptit hic c'est qd il n'y a qu'un seul octet !

Voici le niveau original

lvl1
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x09, 0x09, 0x00, 0x00,
0x00, 0x00, 0x0A, 0x0A, 0x00, 0x00,
0x00, 0x00, 0x09, 0x09, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x0A, 0x09, 0x00, 0x00,
0x00, 0x00, 0x09, 0x0A, 0x00, 0x00,
0x00, 0x00, 0x09, 0x09, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00

Le niveau pour plus de 'compréhension'

lvl1
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x09, 0x09,
0x00, 0x00, 0x00, 0x00,
0x0A, 0x0A,
0x00, 0x00, 0x00, 0x00,
0x09, 0x09,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x0A,
0x09,
0x00, 0x00, 0x00, 0x00,
0x09,
0x0A,
0x00, 0x00, 0x00, 0x00,
0x09, 0x09,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00

et voici comment je pensais 'compresser' ces données (38 octets au lieu des 72)

paquet de 8,4,2,1
bits 3,2,1,0 (4bits du nibble superieur)

1er ligne
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1 paquet de 8 octets (0)
%1000 0001 0x00 - 0x81,0x00

0x09, 0x09, // 1 paquet de 2 octets (9)
%0010 0001 0x09 - 0x21,0x09

0x00, 0x00, 0x00, 0x00, // 1 paquet de 4 octets (0)
%0100 0001 0x00 - 0x41,0x00

0x0A, 0x0A, // 1 paquet de 2 octets (A)
%0010 0001 0x0A - 0x21,0x0A

0x00, 0x00, 0x00, 0x00, // 1 paquet de 4 octets (0)
%0100 0001 0x00 - 0x41,0x00

0x09, 0x09, // 1 paquet de 2 octets (9)
%0010 0001 0x09 - 0x21,0x09

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, //22 octets
// 2 paquets de 8, 1 paquet de 4, 1 paquet de 2
%1000 0010 0x00 - 0x82,0x00
%0100 0001 0x00 - 0x41,0x00
%0010 0001 0x00 - 0x21,0x00

0x0A, // 1 paquet de 1 octet (a)
%0001 0001 0x0a - 0x11,0x0a

0x09, // 1 paquet de 1 octet (9)
%0001 0001 0x09 - 0x11,0x09

0x00, 0x00, 0x00, 0x00,
%0100 0001 0x00 - 0x41,0x00

0x09, // 1 paquet de 1 octet (9)
%0001 0001 0x09 - 0x11,0x00

0x0A, // 1 paquet de 1 octet (a)
%0001 0001 0x0a - 0x11,0x0a

0x00, 0x00, 0x00, 0x00, // 1 paquet de 4 octetS (0)
%0100 0001 0x00 - 0x41,0x00

0x09, 0x09, // 1 paquet de 2 octets (9)
%0010 0001 0x09 - 0x21,0x09

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 6 octets : 1 paquet de 4 octets, 1 paquet de 2 octets
%0100 0001 0x00 - 0x41,0x00
%0010 0001 0x00 - 0x21,0x00

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 // 1 paquet de 8 octets (0)
%1000 0001 0x00 - 0x81,0x00

Edité par Ricco59 Le 28/11/2021 à 23h32

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 29/11/2021 à 00h16

C'est a peu près ce que fait mon algorithme de compression "RLEp".
La petite particularité, c'est que dans l'entête de chaque paquet, je garde 6 bits pour le nombre d'itérations du pattern (1 à 64) et 2 bits pour le type de pattern :
00 : Un paquet contenant la valeur de référence (0 par défaut). Pas d'autre data.
01 : Un paquet contenant une valeur donnée. Suivi d'un octet avec cette valeur. C'est le cas du RLE classique.
10 : Un paquet contenant une suite de 2 valeurs. Suivi de 2 octets avec ces valeurs.
11 : Un paquet non-compressé. Suivi de tous les octets du paquet.

Avec cette astuce, je passe de 72 octets à 22 (au lieu de 38 avec un RLE classique comme celui de ta propal).

Mais bon, que ce soit mon algo ou le RLE classique, son efficacité il très dépendante du type de donnée.
Je l'ai développé spécifiquement pour les sprites.
Il a l'air de bien marcher sur les 3 levels que tu m'as envoyé, mais il faudrait tester avec tes levels les plus complexes pour s'assurer que tu y gagnes aussi.

Voici l'exemple du Level 1 compressé en RLEp :

Code C :

const u8* lvl1_dat[] = {
// Chunk[0] type:0 len:8
    0x07, 
// Chunk[1] type:1 len:2
    0x41, 0x09, 
// Chunk[2] type:0 len:4
    0x03, 
// Chunk[3] type:1 len:2
    0x41, 0x0A, 
// Chunk[4] type:0 len:4
    0x03, 
// Chunk[5] type:1 len:2
    0x41, 0x09, 
// Chunk[6] type:0 len:22
    0x15, 
// Chunk[7] type:3 len:2
    0xC1, 0x0A, 0x09, 
// Chunk[8] type:0 len:4
    0x03, 
// Chunk[9] type:3 len:2
    0xC1, 0x09, 0x0A, 
// Chunk[10] type:0 len:4
    0x03, 
// Chunk[11] type:1 len:2
    0x41, 0x09, 
// Chunk[12] type:0 len:14
    0x0D, 
};

On est toujours ignorant avant de savoir.

Github

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 29/11/2021 à 19h41

Hello,

Je vais chercher un niveau presque vide et un autre rempli avec plus de 10 tokens différents

A pluch'

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 29/11/2021 à 21h01

Le fichier "lvl3.dat.dts" que tu m'avais envoyé ne fait que 60 octets... j'ai mis du temps à comprendre que je n'avais pas de bug dans mon code.

Du coup je n'ai que level 1 et 5 pour mes tests, ce qui fait pas beaucoup.
Si tu pouvais m'en envoyer 4-5 en binaire, ça serait super.

On est toujours ignorant avant de savoir.

Github

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 30/11/2021 à 16h42

Voici le compresseur : https://github.com/aoineko-fr/CMSX/blob/master/tools/CMSXtk/bin/CMSXzip.exe (click sur download).
Tu peux compresser un fichier binaire en .h avec la commande :

Code BASH :

cmsxzip.exe lvl1.dat.dts -c -rlep -def auto -incdef

-c : Génère un fichier .h
-rlep : Compresse au format RLEp
-def auto : Détermine automatiquement la meilleure valeur par défaut
-incdef : Ajoute la valeur par défaut dans les données (en premier)

La valeur par défaut, c'est celle qui est compressée sur 1 seul byte.
A l'origine, j'utilisais toujours la valeur 0 car dans les sprites c'est la valeur la plus courante.
Pour ton besoin, j'ai ajouté une option pour déterminer automatiquement cette valeur et la stocker dans les données.
Par ex., dans ton Level 5, on compresse mieux si on utilise "16" comme valeur par défaut.

Une fois qu'on a nos données compressées, tu peux la décompresser facilement depuis le MSX.
Le code de décompression se trouve sur :
https://github.com/aoineko-fr/CMSX/blob/master/cmsx/src/compress.c
https://github.com/aoineko-fr/CMSX/blob/master/cmsx/src/compress.h

Les deux defines servent à modifier le comportement de la fonction (ça m'évite de devoir écrire 4 versions de la fonction

) :
USE_COMPRESS_RLEP_DEFAULT : Va lire la valeur par défaut dans les données (le 1er octet). Sinon, la valeur par défaut est 0.
USE_COMPRESS_RLEP_FIXSIZE : Ajoute un paramètre "size" à la fonction qui détermine la taille de donnée à décompresser. Par défaut, j'ajoute un 0 pour marquer la fin des données (comme pour une chaine de caractère) ce qui permet de décompresser sans connaitre la taille des données à l'avance. Si on passe une "size" à la fonction, plus besoin d'ajouter un 0 à la fin des données.
Pour tes besoins, tu dois activer les 2 : récupérer la valeur par défaut dans les données et passer la taille du tableau en paramètre (la taille étant toujours 72).

Pour décompresser :

Code C :

const u8 src[] = { /* ... data ... */ };
u8 dest[72];
 
UnpackRLEpToRAM(src, dst, 72);

Si tu veux, je pourrais te faire une version optimisée pour ton jeu.

On est toujours ignorant avant de savoir.

Github

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 01/12/2021 à 23h56

Hello Guillaume,

Wahoooo, c'est du High Level C coding...

Il faut d'abord que je pige un peu car il y a des syntaxes que je n'ai jamais vues... J'ai encore un sacré chemin à parcourir

Je viens à l'instant de dwnloader sdcc4.1.2 et ... info 218: z80instructionSize() failed to parse line node, assuming 999 bytes 'xor a'

Pour l'instant tout BUUUGGGGG, rien ne va... y'a des jours comme ça

Merci beaucoup Guillaume

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 02/12/2021 à 09h55

SDCC 4.1.2 ou SDCC 4.1.12 ?
C'est quoi la dernière version que tu utilisais avant ?

Ceci dit, il n'est pas "nécessaire" de mettre à jour ta version SDCC maintenant.

On est toujours ignorant avant de savoir.

Github

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 03/12/2021 à 21h01

oops, c'est bien la 4.1.12 (du 1er décembre. Celle du 3 est dispo aussi). J'utilisais la 4.1.0. Je v rester pour le moment avec la 4.1.0 qui me satisfait pleinement

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 03/12/2021 à 22h00

Surtout que tu n'es pas sur un jeu d'action.

On est toujours ignorant avant de savoir.

Github

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 03/12/2021 à 22h04

c vrai

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 03/12/2021 à 22h18

Voici une version sans les defines, adaptée à tes besoins.

Code C :

 
typedef unsigned char    u8;    ///< 8 bits unsigned integer type
typedef unsigned short    u16;    ///< 16 bits unsigned integer type
 
u16 UnpackRLEpToRAM(const u8* src, u8* dst, u8 size)
{
    u16 start = (u16)dst; 
    u8 def = *src++; // Get default value from data (1st byte)
 
    while((dst - start) < size)
    {
        // Unpack chunk header
        u8 type = *src >> 6; // chunk type is store in bits 6 & 7
        u8 count = (*src & 0x3F) + 1; // chunk iteration count is store in bits 0 ~ 5
 
        src++;
        if(type == 0) // Chunk of zeros
        {
            Mem_Set(def, dst, count); // Set X time the same value in RAM at the destination address
        }
        else if(type == 1) // Chunk of same byte
        {
            Mem_Set(*src, dst, count);
            src++;
        }
        else if(type == 2) // Chunk of same 2 bytes
        {
            count <<= 1;
            for(i8 i = 0; i < count; ++i)
                dst[i] = src[i & 0x1];
            src += 2;
        }
        else // type == 3 // Chcunk of uncompressed data
        {
            Mem_Copy(src, dst, count); // Copy data from source address to destination in RAM
            src += count;
        }
        dst += count;
    }
    return (dst - start);
}

Si tu as pas de fonctions pour remplir la mémoire comme le Mem_Set() ou copier une zone mémoire ailleurs en mémoire comme le Mem_Copy(), je peux te les fournir.
Ou sinon, tu peux juste utiliser des boucles for.

On est toujours ignorant avant de savoir.

Github

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 03/12/2021 à 22h21

Je viens de faire un essai sur cmsxzip et il me demande MSVCP140D.dll. Normal docteur ??
Je le DL et je reessaye

Edité par Ricco59 Le 03/12/2021 à 22h22

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 03/12/2021 à 22h38

Me revoilou

J'ai mis ce DLL dans le répertoire de la commande puis je l'ai déplacé dans le répertoire system32 et c'est pareil. J'ai :
"L'application n'a pas réussi à démarrer correctement (0xc000007b)..."
Je suis sous Win8.1

Je continue mon debuggage

A pluch'

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

aoineko

Conseiller Municipal

Rang

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2694

Le 04/12/2021 à 01h46

Je suis sous Windows 10. Je vais checker...

EDIT : C'était une version "debug" qui nécessite surement les DLL de VisualStudio. J'ai remplacé l'EXE par une version "release"... ça devrait être mieux.

On est toujours ignorant avant de savoir.

Github

Ricco59

Villageois

Rang

Inscrit le : 02/01/2021 à 11h22

Messages: 248

Le 04/12/2021 à 09h28

c good

Tous mes travaux sont centralisés sur mon piti blog : https://ricco59.blogspot.com/

E-mail

MSX Village forum

La Place des Développeurs Compression / Decompression de datas vers ram