Bug BitmapPut - Page 1

J'ai un bug pas clair avec cette fonction. C'est honteux !
J'essaye de faire une fonction pour deplacer une portion de l'ecran definie par le rectangle (x0,y0,x1,y1) vers la position (x2,y2).
C'est hitoire de faciliter l'implementation du Scrolling en TI-Basic.

Je sais que c'est lent les Bitmap{ Get, Put }, n'empeche que ca foire meme lorsque j'utilise une variable pointeur locale
que j'alloue pour copier une partie de l'ecran.

C'est quoi la methode rapideque vous utiliser ?
Me dites pas que vous le faite a coup de memcpy dans une bouble for

tiens je viens de retrouver un gros topic dans lequel ca ete debattu de long en large ici.
J 'avais completement oublie que le moteur de recherche etait fonctionnel. Je vais donc me faire des Memcpy pour mon scrolling de plateau.


Une question tout de meme :
Lorsqu'on copie des donnees, est-meilleur d'utiliser des (long *) plutot que des (char *) ou (short *) pour la copie ?

d'apres le code de Pollux, je dirai que oui :

void memmove_even(void *p,void *q,unsigned int size) { 
    unsigned int n=size>>3; 
    if (p<q) { // forward 
#define move4() *((long *)p)++=*((long *)q)++ 
#define move2() *((int  *)p)++=*((int  *)q)++ 
        if (n--) 
            do 
                move4(),move4(); 
            while (n--); 
        if (size&4) 
            move4(); 
        if (size&2) 
            move2(); 
#undef move4 
#undef move2 
    } else { // backward 
        p+=size; q+=size; 
#define move4() *--((long *)p)=*--((long *)q) 
#define move2() *--((int  *)p)=*--((int  *)q) 
        if (n--) 
            do 
                move4(),move4(); 
            while (n--); 
        if (size&4) 
            move4(); 
        if (size&2) 
            move2(); 
#undef move4 
#undef move2 
    } 
}

Ce qui veux surement dire que memcpy du TIOS procede de facon similaire.

si tu lis/écrit depuis des adresses paires, oui, les longs c'est "mieux" : plus rapide
(par contre, long ou short depuis ou vers une adresse impaire, tu es bon pour une address error)

andoh_wilfried
: J'ai un bug pas clair avec cette fonction. C'est honteux !

en fait si ça n'a pas été corrigé depuis ams 2.05, y'a pas qu'un seul bug pas clair avec cette fonction... ^^

J'essaye de faire une fonction pour deplacer une portion de l'ecran definie par le rectangle (x0,y0,x1,y1) vers la position (x2,y2). C'est hitoire de faciliter l'implementation du Scrolling en TI-Basic.

ça risque d'être super lent (même pour du basic)

heu je suis pas sur que le long soit plus rapide que les short sur le 68000 (le bus de donnée eset de 16bits, pas de 32bits)

oué, mais un long plus rapide que deux shorts, c'est probable, non ?
deux move sur un short = deux instructions + deux lectures/écritures
un move sur un long = une seule instruction + une lecture/écriture (plus longue, peut-etre)

c'est pas genre 8 unités de temps pour un move long et 6 pour un move short (donc, 12 pour deux move short), ou dans le genre - en ordre de grandeur ?
(un mec qui code en asm saurait surement mieux que moi ^^ )

>heu je suis pas sur que le long soit plus rapide que les short sur le 68000 (le bus de donnée eset de 16bits, pas de 32bits)
Si car il n'y a qu'un seul decodage d'instruction.

deux move sur un short = deux instructions + deux lectures/écritures un move sur un long = une seule instruction + une lecture/écriture (plus longue, peut-etre)

deux move sur un short = deux instructions + deux lectures/écritures
un move sur un long = une seule instruction + deux lectures/écritures

^^

ah, ok ^^

Merci a tous. Je peux donc conclure que tout debut de fichier dans la VAT est localise a une addresse paire.

Vertyos -> ça risque d'être super lent (même pour du basic)

Je vais tester mais bon ca sera peut-etre plus rapide si j'evite de reallouer un buffer sytematiquement a chaque scrolling.
Je vais utiliser ma variable d'ecran virtuel ( qui est alloue une fois pour toute ) comme buffer temporaire.

Tu n'as pas besoin de buffer pour faire du scrolling.
Implémente le scrolling proprement, et tu n'auras pas le problème du tout. En plus, ça sera quasiment 2x plus rapide.

c'est vrai que la, j'ai dit une betise. Merci spectras
Je commence par deplace le contenu de l'ecran en commencant
par la zone la plus proche de la portion d'ecran non incluse dans le scrolling.

spectras :
Tu n'as pas besoin de buffer pour faire du scrolling. Implémente le scrolling proprement, et tu n'auras pas le problème du tout. En plus, ça sera quasiment 2x plus rapide.

et même bien plus que ça, par rapport à une solution avec des BitmapPut ^^

J'ai reflechi a la routine ; c'est purement de la recopie bit a bit.
Y a pas moyen d'utiliser des (long *), (short *) ou (char *) pour des recopies rapides
comme le fait Pollux dans son code.

ça dépend, pour les scrollings verticaux si, pour les horizontaux va falloir passer par un truc en asm pour que ça soit vraiment rapide

Non, l'important n'est pas vraiment de faire de l'asm, c'est surtout de bien comprendre quels sont les algorithmes les plus efficaces (l'asm a surtout pour avantage de permettre de comprendre les raisons pour lesquelles un algorithme est efficace ou non).

Par exemple un algorithme qui est tout à fait honnête, et qui sera tout aussi rapide que l'équivalent en asm optimisé :

void *src = ... à calculer ..., *dst = écran_virtuel;
int shift = ... à calculer ...;

unsigned long *src_even = src, *src_odd = src+2;
unsigned short *dst_ptr = dst;


while (nb_lines--) {
    ... calculer le nombre de mots à afficher ...

    // La boucle interne :
    do {
        *dst_ptr++ = *src_even++ >> shift;
        *dst_ptr++ = *src_odd++ >> shift;
    } while (n--);

    ... ajuster les pointeurs pour la ligne suivante ...
}

(je ne mets pas le détail des initialisations, à toi de les retrouver )

approche intéressante, mais je me demande si
1) elle fonctionne inplace ? il me semble que non.
2) gcc saura optimiser les deux lectures depuis even et odd, sachant qu'en plus il n'est pas exclus au moment la compilation que dst_ptr soit un alias pour src_odd/src_even

spectras :
approche intéressante, mais je me demande si 1) elle fonctionne inplace ? il me semble que non.

Non, c'est avec un buffer externe, ce qui est souvent une solution assez logique pour un scrolling. Dans le cas contraire ça ne serait pas très difficile de la modifier pour que ça fonctionne sur place : par exemple pour un scrolling horizontal, il suffit, au lieu de stocker directement dans *dst_ptr++, de le faire d'abord passer par N registres différents (où N est le nombre maximal de mots de 16 bits par lequel on voudra décaler). Ce n'est pas un surcoût en temps tant que N <~ 8, ça peut juste vouloir dire qu'il faudra dérouler la boucle ^^

2) gcc saura optimiser les deux lectures depuis even et odd, sachant qu'en plus il n'est pas exclus au moment la compilation que dst_ptr soit un alias pour src_odd/src_even

Qu'est-ce que tu veux dire ? Il n'est pas question d'optimiser, c'est justement là l'intérêt :

  move.l (a1)+,d0
  lsr.l d1,d0
  move.w d0,(a0)+
  move.l (a2)+,d0
  lsr.l d1,d0
  move.w d0,(a0)+

Je ne vois pas ce qui pourrait être optimisé là-dedans ? (par contre si le compilateur était trop malin il serait capable de le désoptimiser en se rendant compte que (void *)src_odd = (void *)src_even + 2, mais ça ne ferait pas perdre plus de 2 cycles par mot de 16 bits)

Ok pour le 1)

Pour le 2) tu lis deux fois le word de chevauchement entre even et odd à chaque tour de boucle. C'est voulu ? O_o

Ben oui
Le moindre swap rajouterait un overhead de 4 cycles, ce qui fait que déjà ça serait au moins aussi lent que relire un mot "en trop" à chaque mot à shifter. Sans compter qu'évidemment il faudrait appliquer le swap avant le lsr.l, donc sauvegarder le contenu du registre avant le shift, ça ferait perdre encore 4 cyles ^^

Enfin cela dit si on veut vraiment que ça soit rapide il faudrait distinguer les cas shift<8 et shift>=8 pour pas que le shift prenne trop de temps (en faisant une rotation à droite dans le cas shift>=8).

Par contre je viens de trouver une méthode assez nettement meilleure que ça, surtout dans le pire des cas (au moins 25% plus rapide), mais elle utilise bcp de bouts de registres (i.e. manipulation des 16 bits de poids faible tout en conservant les 16 bits de poids fort), donc ça aura du mal à passer en C pur avec les compilos actuels

Vas-y poste la quand même

Je ne sais pas si ça t'intéressera, elle n'a pas du tout la prétention d'être state-of-the-art ou quoi que ce soit, je dis juste qu'elle est plus efficace que ./17

// d3 <= 8
// d4 = (1<<d3)-1
// d5 = ~d4

  move.w (a1)+,d0
  rol.l d3,d0    // ou ror/swap si shift>8
  and.w d4,d0

boucle {

  move.l (a1)+,d1
  rol.l d3,d1    // ou ror/swap si shift>8
  move.l d1,d2
  and.w d4,d2
  and.w d5,d1
  or.w d1,d0
  move.l d0,(a0)+

  ... idem en échangeant d0 et d2 ...

}

soit 48+2n cycles pour afficher 32 nouveaux pixels, à comparer avec 28+2m cycles pour afficher 16 pixels avec la méthode de ./17 ^^

(le pire des cas est atteint pour n=9, donc 66 cycles/32 bits avec cette méthode, comparé au pire des cas m=8 -- 44 cycles/16 bits = 88 cycles/32 bits avec ./17 modifié pour que shift<=8 ; donc en fait c'est 33% plus rapide )

Tu sais y a pas gd chose à connaître, le plus important c'est de comprendre la place que prennent les instructions... (ou, autrement dit, la quantité de transferts mémoire nécessaire pour l'exécution de chaque instruction)

Une fois que tu connais ça, y a vraiment très très peu d'exceptions à la règle "nb_cycles = nb_accès_bus * 4" : les shifts, les opérations arithmétiques/logiques sur des longs, les branchements, les modes d'adressage exotiques, et c'est à peu près tout...

./23> Ah ok, je croyais que c'était un algo facilement implémentable en C.

> Par contre je viens de trouver une méthode assez nettement meilleure
"nouveau" ? Ah bon !

Et en français ça donne quoi ?

Bah elle est pas "nouvelle" dans le sens où elle a déjà été exploitée par des programmeurs TI.
Je pense que c'est ça qu'il a voulu dire.

Comme je l'ai dit "elle n'a pas du tout la prétention d'être state-of-the-art ou quoi que ce soit", et encore moins la prétention d'être nouvelle ^^