Y a-t-il un code raisonnablement rapide qui peut m'aider à rechercher rapidement un grand bitmap (quelques mégaoctets) pour des courses de zéro contigu ou d'un bits?
Par "raisonnablement rapide", je veux dire quelque chose qui peut tirer parti de la taille du mot de la machine et de comparer des mots entiers à la fois, au lieu de faire une analyse bit-bit qui est horriblement lente (comme on le fait avec C'est très utile pour E.G. Recherche dans le bitmap d'un volume d'espace libre (pour la défragmentation, etc.). vecteur
3 Réponses :
Windows a un Mais j'avais besoin du code pour cela il y a parfois, et donc je l'ai écrit ici (avertissement, c'est un peu laid): J'ai L'opération fondamentale pour l'ensemble de la chose est de pouvoir - rapidement - trouver le Longueur d'une course de bits: tout le reste doit être facile à construire sur ceci, compte tenu de sa polyvalence. J'ai essayé d'inclure un code SSE , mais cela n'a pas sensiblement amélioré la performance. Cependant, en général, le code est plusieurs fois plus rapide que de faire une analyse bit-budge, alors je pense que cela pourrait être utile. Il doit être facile à tester si vous pouvez obtenir une prise de rtl_bitmap < / a> Structure de données On peut utiliser avec ses API.
https://gist.github.com/3206128 inverse ). Mais une version récente (légèrement différente de celle-ci) semblait être utilisable pour moi, alors ça vaut la peine d'essayer. Vecteur
Je ne peux pas comprendre comment bien faire directement sur des mots de mémoire, donc j'ai constitué une solution rapide qui fonctionne sur des octets; Pour plus de commodité, croquons l'algorithme pour compter des contigus:
Construisez deux tables de taille 256 où vous écrirez pour chaque nombre compris entre 0 et 255, le nombre de suivi 1 au début et à la fin de l'octet. Par exemple, pour le numéro 167 (10100111 en binaire), mettez 1 dans la première table et 3 dans la deuxième table. Appelons la première table BBEG et la deuxième courbe de table. Ensuite, pour chaque octet B, deux cas: s'il s'agit de 255, ajoutez 8 à votre somme actuelle de votre ensemble contiguë actuel de ceux et vous êtes dans une région de ceux. D'autre, vous mettez fin à une région avec BBEG [B] des bits et commencez une nouvelle avec les bits de courbure [B]. Selon les informations que vous voulez, vous pouvez adapter cet algorithme (c'est une raison pour laquelle je ne mettez pas ici aucun code, je ne sais pas quelle sortie vous voulez).
Un défaut est qu'il ne compte pas (petit) ensemble contigu de ceux à l'intérieur d'un octet ...
Outre cet algorithme, un ami me dit que s'il s'agit de la compression de disque, recherchez simplement des octets différents de 0 (zone de disque vide) et 255 (zone de disque complète). C'est une heuristique rapide de construire une carte de quels blocs que vous devez compresser. Peut-être que c'est au-delà de la portée de ce sujet ...
sonne comme ceci pourrait être utile:
http : //www.agregued.org/magic/#population%20Count%20%28ONES%20Count%29
et
http://www.agregue.org/magic/#leading%20zero%20Count --/ a> p> Vous ne dites pas si vous vouliez faire une sorte de rle ou de compter simplement des zéros d'octets et que des bits (comme 0B1001 devraient renvoyer 1x1 2x0 1x1). P> Une table de recherche plus une algorithme de swar pour une vérification rapide pourrait vous donner cette information facilement.
Un peu comme ceci: p> Le lut devra être construit en fonction de votre algorithme prévu. Si vous souhaitez compter le nombre de 0 et 1 contigus dans le mot, vous le ferez comme suit: P> for (int i = 0; i < sizeof(lut); i++)
lut[i] = countContiguousZero(i); // Or countContiguousOne(i)
// The implementation of countContiguousZero can be slow, you don't care
// The result of the function should return the largest number of contiguous zero (0 to 15, using the 4 low bits of the byte, and might return the position of the run in the 4 high bits of the byte
// Since you've already dismissed word = 0, you don't need the 16 contiguous zero case.
Vous ne pouvez pas traiter votre tableau en tant que tableau d'entiers et comparer entier à zéro?
@Andrew: Cela dépend en quelque sorte de ce que vous essayez de réaliser ... Les bits peuvent ne pas être alignés 8 bits à la fois.
Vous pouvez comparer 6 octets (si le BMP est un fichier image couleur: 6 octets est deux pixels contiguous) avec un tableau de 6 zéros.
@eHarvest: Je ne parle pas de photos! Ceci est complètement sans rapport avec des images raster. Je parle de bits de tableaux, c'est-à-dire un tableau de bits.
Désolé, j'ai lu votre question trop vite ...