Je veux envoyer des noms de fonction à partir d'un système intégré faible à l'ordinateur hôte pour le débogage. Étant donné que les deux sont connectés par RS232, ce qui est court sur la bande passante, je ne veux pas envoyer le nom de la fonction littéralement. Il y a quelque 15 caractères longs longs noms de fonction, et je veux parfois envoyer ces noms à un tarif assez élevé.
La solution que j'ai pensée, était de trouver une fonction de hachage qui choisirait ces noms de fonction à un seul octet et Envoyer cet octet seulement. L'ordinateur hôte scannerait toutes les fonctions de la source, calculerait leur hachage à l'aide de la même fonction, puis traduirait le hachage sur la chaîne d'origine.
La fonction de hachage doit être
Évidemment, il n'a pas besoin d'être sécurisé par aucun moyen, uniquement sans collision. Donc, je ne pense pas que l'utilisation de la fonction de hachage liée à la cryptographie vaut leur complexité.
Un exemple de code: L'hôte serait alors capable de Présentez-moi avec la liste des fois où la fonction existe une fonction de hachage connue qui contient les conditions ci-dessus? myfunc est exécutée.
8 Réponses :
hmm avec seulement 256 valeurs possibles, puisque vous allez analyser votre code source pour connaître toutes les fonctions possibles, peut-être que la meilleure façon de le faire serait d'attribuer un numéro à chacune de vos fonctions ???
Une vraie fonction de hash ne fonctionnerait probablement pas car vous n'avez que 256 hachages possibles. Mais vous souhaitez cartographier au moins 26 ^ 15 valeurs possibles (en supposant que les noms de fonctions insensibles par lettre). Même si vous limitez le nombre de chaînes possibles (en appliquant une mise en forme obligatoire), vous seriez difficile pour obtenir des noms significatifs et une fonction de hachage valide.
Non, il n'y a pas.
Vous ne pouvez pas créer de code de hasch sans collision, ni même près d'elle, avec un hachage de huit bits. Si vous autorisez des chaînes plus longues qu'un caractère, vous avez plus de chaînes possibles que des codes de hash possibles.
Pourquoi ne pas simplement extraire les noms de fonction et donner à chaque nom de la fonction un identifiant? Ensuite, vous n'avez besoin que d'une table de recherche de chaque côté du fil.
(Comme d'autres personnes ont montré, vous pouvez générer un algorithme de hachage sans collision si vous avez déjà toutes les noms de fonction, mais il est plus facile de simplement affecter un numéro à chaque nom pour créer une table de recherche ...)
Pourquoi les bowvotes? Si vous ne dites pas ce que c'est que vous n'aimez pas, c'est vraiment inutile.
Le hachage 8 bits pourrait être bien en fonction du nombre de chaînes - selon le Paradox d'anniversaire Cela devrait être assez réalisable pour dire 20 chaînes, et si vous recherchez assez fort, vous pouvez espérer trouver un hachage 8 bits sans collision pour dire 40 ou 50 chaînes. Mais si vous ne voulez pas passer des efforts à la recherche d'une fonction de hachage sans collision, vous avez raison, vous voudriez probablement un hachage de 2 à 4 octets.
Pourquoi le bowvote? Si vous n'expliquez pas ce que vous pensez être faux, cela ne peut pas améliorer la réponse.
Essayez Minimal Perfect Hashing :
Un hachage parfait minimal garantit que n clés fera mapper à 0..n-1 sans collision.
C code est inclus.
Cela ne fonctionne pas sans d'abord obtenir tous les noms de fonction.
Oui, vous ne pouvez faire de hasard que si vous connaissez toutes les chaînes à l'avance. Si ce n'est pas le cas, une approche consiste à utiliser une table de hachage pour gérer les collisions, puis transmet l'index de l'entrée dans la table de hachage.
Vous pourriez également être capable de coaxer GPERF ou similaire à la signature à la compilation, réduisant ainsi le coût de calcul à 0
Vous pouvez utiliser un Huffman Tree pour abréger votre fonction Noms En fonction de la fréquence, ils sont utilisés dans votre programme. La fonction la plus courante pourrait être abrégée à 1 bit, moins courante à 4-5, très rares fonctions à 10-15 bits, etc. Un arbre de Huffman n'est pas très difficile à mettre en œuvre, mais vous devrez faire quelque chose à propos de l'alignement des bits.
Si vous avez un moyen de suivre les fonctions dans votre code (c'est-à-dire un fichier texte généré au moment de l'exécution), vous pouvez simplement utiliser les emplacements de mémoire de chaque fonction. Pas exactement un octet, mais plus petit que tout le nom et garanti d'être unique. Cela a l'avantage supplémentaire de bas frais généraux. Tout ce que vous auriez besoin de "décoder" l'adresse est le fichier texte qui correspond à des adresses aux noms réels; Cela pourrait être envoyé à l'emplacement distant ou, comme je l'ai mentionné, stocké sur la machine locale.
C'est comme ça que je le ferais. Vous devriez pouvoir utiliser les informations de débogage dans le binaire compilé pour extraire le nom de la fonction, sans avoir besoin d'une table supplémentaire.
Dans ce cas, vous pouvez simplement utiliser un puis dans les fonctions: Enum pour identifier les fonctions. Déclarez des identifiants de fonction dans certains fichiers d'en-tête:
Si l'expéditeur et le récepteur partagent le même ensemble de noms de fonction, ils peuvent créer des hashtables identiques à partir de ceux-ci. Vous pouvez utiliser le chemin emprunté pour accéder à un élément de hachage pour communiquer ceci. Cela peut être {position de départ + nombre de sauts} pour communiquer ceci. Cela prendrait 2 octets de bande passante. Pour une table de taille fixe (sondage de lineaire), seul l'index final est nécessaire pour adresser une entrée.
Remarque: lors de la construction des deux tables de hachage "synchrones", l'ordre d'insertion est important; -)
Décrit ici est un moyen simple de la implémenter vous-même: http : //www.devcodenote.com/2015/04/collision-bee-string-hashing.html
Voici un extrait de l'article:
Il tire son inspiration à partir de la manière dont les nombres binaires sont décodés et convertis au format de nombres décimaux. Chaque représentation de chaînes binaires mappe de manière unique sur un nombre au format décimal.
Si dire que nous avons un jeu de caractères de lettres majuscules anglais, la longueur de l'ensemble de caractères est 26 où a peut être représenté par le numéro 0, b par le numéro 1, c par le numéro 2 et ainsi de suite jusqu'à z Au numéro 25. Maintenant, chaque fois que nous voulons mapper une chaîne de ce caractère défini sur un numéro unique, nous effectuons la même conversion que nous le faisions en cas de format binaire
OK, un seul octet signifie que vous pouvez avoir un maximum de 256 noms de fonction différents. Est-ce vrai pour votre système intégré? En outre, si tous les noms de fonction sont décidés et statiques, pourquoi n'utilisez-vous pas d'énumération pour mapper une seule fonction?
Avez-vous envisagé d'utiliser une ou plusieurs des fonctions de hachage à usage général suivantes: /hashfunctions/index.html