Quando una struct può essere sottoposta a hashing sicuro come una matrice di byte?

Question

Per le strutture in cui l'uguaglianza indica l'uguaglianza di tipo e byte più derivato identico di ciascun membro dati, quando, se possibile, la struttura può essere sottoposta a hash in modo sicuro come una matrice di byte?

Questo documento

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3333.html

alla voce "Hashing oggetti come array di byte" suggerisce che le strutture con imbottitura non possono essere hashing sicuro come una matrice di byte.

È un test esplicito per il riempimento richiesto per hash in modo sicuro una struttura come una matrice di byte? È sufficiente?

In tal caso, il seguente schizzo illustra correttamente tale test?

#include <cstddef> 
#include <iostream> 

struct A 
{ 
    int i; 
    float f; 
    char c; 
}; 
// hashing would start at offs_i (possibly hopping over a v-table) and end at 
// offs_c + sizeof(char) 

int main() 
{ 
    const std::size_t size_A = sizeof(A); 
    const std::size_t size_int = sizeof(int); 
    const std::size_t size_float = sizeof(float); 
    const std::size_t size_char = sizeof(char); 
    const std::size_t offs_i = offsetof(A, i); 
    const std::size_t offs_f = offsetof(A, f); 
    const std::size_t offs_c = offsetof(A, c); 

    bool padded = false; 
    if (offs_f != size_int) 
     padded = true; 
    else if (offs_c != size_int + size_float) 
     padded = true; 

    std::cout << "padded? " << std::boolalpha << padded << std::endl; 
} 

Se una struct ha imbottitura, non v'è alcun modo per soluzione per consentire hashing come una matrice di byte, ad esempio azzerando i bit di riempimento?

"Sicuro" qui indica due strutture che confrontano lo stesso hash con valori identici.

Answer 1

Quasi mai. Lo standard non definisce come viene implementata l'ereditarietà, ad es. con puntatori vtable, quindi non vi è alcuna garanzia che due classi che hanno il medesimo tipo di derivazione uguale abbiano dati relativi all'ereditarietà specifica dell'implementazione uguali.

Inoltre, poiché non sono POD, l'offsetof non è garantito per funzionare o produrre risultati significativi- Credo che sia in realtà solo UB.

Il lungo e breve è, non preoccupatevi di provare a trattare strutture come matrici di byte perché non sono.

Per quanto riguarda le sue intenzioni sulla carta, è più probabile una concessione ad alcune delle rabbiose "er mah gerd performances!" cani nel comitato piuttosto che una cosa reale che vuole fare.

Answer 2

Il documento si fa riferimento prety molto stati i requisiti:

is_trivially_copyable<T>::value && 
is_standard_layout<T>::value && 
is_contiguous_layout<T>::value 

che devono valere in modo ricorsivo per la struct stesso e tutti i membri.

I primi due controlli fanno già parte della libreria standard ed è possibile implementare is_contiguous_layout<T>::value da soli. Come base dovrebbe essere sufficiente confrontare la somma delle dimensioni dei suoi membri con la dimensione della struttura stessa. Non penso che controllare l'offset sia effettivamente necessario.

Questo dovrebbe funzionare sulle "solite" piattaforme (CHAR_BIT == 8, 2-complemento) se il tuo tipo è composto solo da tipi di interi. Tuttavia, non sono sicuro che, se funziona anche con bool e numeri in virgola mobile, credo che lo standard non imponga una mappatura bidirezionale unica tra il valore di una variabile e la sua rappresentazione di bit.

MODIFICA: mi sono appena reso conto che non è possibile soddisfare la condizione of same most derived type, se nella classe derivata non si aggiungono membri o se si confrontano due classi distinte che hanno gli stessi membri. Quindi dovresti tenere conto del tipo separatamente.

Answer 3

Se la struttura è POD, si dovrebbe essere in grado di bzero o memcpy su 0 per l'intera struttura all'inizializzazione, quindi l'hashing come una matrice di byte dovrebbe essere soddisfacente ed efficiente.