Recherche efficace de la position ‘1 dans un tableau de bits

Je câble un programme qui teste un ensemble de fils pour détecter les circuits ouverts ou les courts-circuits. Le programme, qui fonctionne sur un AVR, pilote un vecteur de test (“1” en marche) sur les fils et reçoit le résultat. Il compare ce vecteur résultant aux données attendues qui sont déjà stockées sur une carte SD ou une EEPROM externe.

Voici un exemple, supposons que nous ayons un ensemble de 8 fils qui sont tous droits, c’est-à-dire qu’ils n’ont pas de jonction. Donc, si nous conduisons 0b00000010, nous devrions recevoir 0b00000010.

Supposons que nous recevions 0b11000010. Cela implique un court-circuit entre le fil 7,8 et le fil 2. Je peux détecter les bits qui m’intéressent par 0b00000010 ^ 0b11000010 = 0b11000000. Cela me dit clairement que les fils 7 et 8 sont en faute, mais comment puis-je trouver la position de ces ‘1 de manière efficace dans une grande masortingce de bits. Il est facile de faire cela avec seulement 8 fils utilisant des masques de bits, mais le système que je développe doit gérer jusqu’à 300 fils (bits). Avant de commencer à utiliser des macros comme celles-ci et à tester chaque bit dans un tableau de 300 * 300 bits, je voulais demander ici s’il existait une solution plus élégante.

#define BITMASK(b) (1 << ((b) % 8)) #define BITSLOT(b) ((b / 8)) #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) #define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) #define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b)) #define BITNSLOTS(nb) ((nb + 8 - 1) / 8) 

Juste pour montrer comment détecter un circuit ouvert. Données attendues: 0b00000010, données reçues: 0b00000000 (le fil n’est pas tiré haut). 0b00000010 ^ 0b00000000 = 0b0b00000010 – le fil 2 est ouvert.

REMARQUE: Je sais que tester 300 fils n’est pas une tâche que la minuscule RAM d’un AVR Mega 1281 peut gérer. C’est pourquoi je vais la diviser en groupes, c’est-à-dire tester 50 fils, comparer, afficher les résultats et avancer.

De nombreuses architectures fournissent des instructions spécifiques pour localiser le premier bit défini dans un mot ou pour compter le nombre de bits définis. Les compilateurs fournissent généralement des éléments insortingnsèques pour ces opérations, de sorte que vous n’avez pas à écrire d’assembly inline. GCC, par exemple, fournit __builtin_ffs , __builtin_ctz , __builtin_popcount , etc., chacun devant mapper sur l’instruction appropriée de l’architecture cible, exploitant le parallélisme au niveau du bit.

Si l’architecture cible ne les prend pas en charge, le compilateur émet une implémentation logicielle efficace. L’approche naïve consistant à tester progressivement le vecteur dans le logiciel n’est pas très efficace.

Si votre compilateur ne les implémente pas, vous pouvez toujours coder votre propre implémentation en utilisant une séquence de Bruijn .

À quelle fréquence vous attendez-vous à des défauts? Si vous ne les attendez pas si souvent, il semble inutile d’optimiser le cas “faute existe” – la seule partie qui compte vraiment pour la rapidité est le cas “aucune faute”.

Pour optimiser le cas sans faute, il suffit de XOR le résultat réel avec le résultat attendu et un test d’ input ^ expected == 0 pour voir si des bits sont définis.

Vous pouvez utiliser une stratégie similaire pour optimiser le cas de “quelques erreurs”, si vous vous attendez à ce que le nombre d’erreurs soit généralement faible quand ils existent – masquez l’ input ^ expected valeur input ^ expected pour obtenir uniquement les 8 premiers bits, uniquement le second. 8 bits, etc., et comparez chacun de ces résultats à zéro. Ensuite, il vous suffit de rechercher les bits définis dans ceux qui ne sont pas égaux à zéro, ce qui devrait limiter l’espace de recherche à une tâche pouvant être effectuée assez rapidement.

Vous pouvez utiliser une table de recherche. Par exemple, la table de correspondance log-base-2 de 255 octets peut être utilisée pour rechercher le bit le plus significatif dans un octet:

 uint8_t bit1 = log2[bit_mask]; 

où log2 est défini comme suit:

 uint8_t const log2[] = { 0, /* not used log2[0] */ 0, /* log2[0x01] */ 1, 1 /* log2[0x02], log2[0x03] */ 2, 2, 2, 2, /* log2[0x04],..,log2[0x07] */ 3, 3, 3, 3, 3, 3, 3, 3, /* log2[0x08],..,log2[0x0F */ ... } 

Sur la plupart des processeurs, une table de recherche comme celle-ci ira à la ROM. Mais AVR est une machine de Harvard et placer des données dans un espace de code (ROM) nécessite une extension spéciale non standard, qui dépend du compilateur. Par exemple, le compilateur IAR AVR doit utiliser le mot clé étendu __flash. Dans WinAVR (GNU AVR), vous devez utiliser l’atsortingbut PROGMEM, mais il est plus complexe que cela, car vous devez également utiliser des macros spéciales pour lire à partir de l’espace programme.

Je pense qu’il n’y a qu’une seule façon de faire cela:

  • Créez un tableau sur “en dehors de”. Chaque élément du tableau peut par exemple correspondre à un registre de ports à 8 bits.
  • Envoyez les données à l’extérieur sur les fils.
  • Relisez ces données en tant que “indata”.
  • Stockez l’indata dans un tableau mappé de la même manière que la sortie.
  • Dans une boucle, XOR chaque octet d’extra de données avec chaque octet d’indata.

Je recommanderais fortement les fonctions inline au lieu de ces macros.

Pourquoi votre MCU ne peut-elle pas gérer 300 fils?

300/8 = 37,5 octets. Arrondi à 38. Il doit être stocké deux fois, en sortie ,ata et indata, 38 * 2 = 76 octets.

Vous ne pouvez pas économiser 76 octets de RAM?

Je pense que vous manquez la forêt à travers les arbres. On dirait un test de lit d’ongles. Commencez par tester certaines hypothèses: 1) Vous savez quelles broches doivent être sous tension pour chaque broche testée / sous tension. 2) vous avez une netlist traduite pour l’étape 1 dans un fichier sur sd

Si vous opérez à la fois en octets et en octets, cela simplifie le problème. Si vous activez une broche, un modèle attendu est stocké dans votre fichier. Commencez par trouver les octets incompatibles. identifier les épingles incompatibles dans l’octet; stockez enfin la broche sous tension avec les numéros de broche défectueux.

Vous n’avez pas besoin d’un tableau pour la recherche ou des résultats. idée générale:

 numwires=300; numbytes=numwires/8 + (numwires%8)?1:0; for(unsigned char currbyte=0; currbyte