C entrevista de trabajo – casting y comparación

Question 1

Me enfrenté a una pregunta difícil (en mi opinión). necesitaba comparar dos direcciones MACde la manera más eficiente.

El único pensamiento que cruzó mi mente en ese momento fue la solución trivial: una for loop, y comparando locaciones, y así lo hice, pero el entrevistador apuntaba al casting.

La definición MAC:

typedef struct macA {
   char data[6];
} MAC;

Y la función es (la que me pidieron implementar):

int isEqual(MAC* addr1, MAC* addr2)
{
    int i;

    for(i = 0; i<6; i++)
    {
        if(addr1->data[i] != addr2->data[i]) 
            return 0;
    }
    return 1;
}

Pero como se mencionó, él apuntaba al casting.

Es decir, para convertir de alguna manera la dirección MAC dada a un int, comparar ambas direcciones y regresar.

Pero al lanzar, int int_addr1 = (int)addr1;, solo se emitirán cuatro bytes, ¿verdad? ¿Debería revisar los restantes? ¿Significa las ubicaciones 4 y 5?

Ambas cosas char y int son tipos enteros, por lo que la conversión es legal, pero ¿qué sucede en la situación descrita?

Question 2

Si él está realmente insatisfecho con este enfoque (que es esencialmente un pedo cerebral, ya que no está comparando megabytes o gigabytes de datos, por lo que uno no debe preocuparse por la “eficiencia” y la “velocidad” en este caso), simplemente dígale que confía en la calidad y la velocidad de la biblioteca estándar:

int isEqual(MAC* addr1, MAC* addr2)
{
    return memcmp(&addr1->data, &addr2->data, sizeof(addr1->data)) == 0;
}

Question 3

Si su entrevistador exige que produzca un comportamiento indefinido, probablemente buscaría un trabajo en otro lugar.

El enfoque inicial correcto sería almacenar la dirección MAC en algo como un uint64_t, al menos en la memoria. Entonces las comparaciones serían triviales e implementables de manera eficiente.

Question 4

Hora del vaquero:

typedef struct macA {
   char data[6];
} MAC;

typedef struct sometimes_works {
   long some;
   short more;
} cast_it

typedef union cowboy
{
    MAC real;
    cast_it hack;
} cowboy_cast;

int isEqual(MAC* addr1, MAC* addr2)
{
     assert(sizeof(MAC) == sizeof(cowboy_cast));  // Can't be bigger
     assert(sizeof(MAC) == sizeof(cast_it));      // Can't be smaller

     if ( ( ((cowboy_cast *)addr1)->hack.some == ((cowboy_cast *)addr2)->hack.some )
       && ( ((cowboy_cast *)addr1)->hack.more == ((cowboy_cast *)addr2)->hack.more ) )
             return (0 == 0);

     return (0 == 42);
}

Question 5

No hay nada de malo en una implementación eficiente, por lo que sabe, se ha determinado que se trata de un código activo que se llama muchas veces. Y en cualquier caso, está bien que las preguntas de la entrevista tengan restricciones extrañas.

AND lógico es a priori una instrucción de bifurcación debido a la evaluación de cortocircuito, incluso si no se compila de esta manera, así que evitémoslo, no lo necesitamos. Tampoco necesitamos convertir nuestro valor devuelto en un verdadero bool (verdadero o falsono 0 o cualquier cosa que no sea cero).

Aquí hay una solución rápida en 32 bits: XOR capturará las diferencias, O registrará la diferencia en ambas partes, y NO negará la condición en IGUAL, no DESIGUAL. LHS y RHS son cálculos independientes, por lo que un procesador superescalar puede hacer esto en paralelo.

int isEqual(MAC* addr1, MAC* addr2)
{
    return ~((*(int*)addr2 ^ *(int*)addr1) | (int)(((short*)addr2)[2] ^ ((short*)addr1)[2]));
}

EDITAR

El propósito del código anterior era mostrar que esto se podía hacer de manera eficiente sin bifurcarse. Los comentarios han señalado que C++ clasifica esto como un comportamiento indefinido. Si bien es cierto, VS maneja esto bien. Sin cambiar la definición de estructura del entrevistador y la firma de la función, para evitar un comportamiento indefinido, se debe hacer una copia adicional. Entonces, la forma de comportamiento no indefinido sin ramificación pero con una copia adicional sería la siguiente:

int isEqual(MAC* addr1, MAC* addr2)
{
    struct IntShort
    {
        int   i;
        short s;
    };

    union MACU
    {
        MAC addr;
        IntShort is;
    };

    MACU u1;
    MACU u2;

    u1.addr = *addr1; // extra copy
    u2.addr = *addr2; // extra copy

    return ~((u1.is.i ^ u2.is.i) | (int)(u1.is.s ^ u2.is.s)); // still no branching
}

Question 6

Esto funcionaría en la mayoría de los sistemas y sería más rápido que su solución.

int isEqual(MAC* addr1, MAC* addr2)
{
    return ((int32*)addr1)[0] == ((int32*)addr2)[0] &&  ((int16*)addr1)[2] == ((int16*)addr2)[2];
}

estaría en línea muy bien también, podría ser útil en el centro del ciclo en un sistema donde puede verificar que los detalles sean viables.

Question 7

Solución de fundición no portátil.

En una plataforma que uso (basada en PIC24), hay un tipo int48por lo que haciendo una suposición segura char es de 8 bits y los requisitos de alineación habituales:

int isEqual(MAC* addr1, MAC* addr2) {
  return *((int48_t*) &addr1->data) == *((int48_t*) &addr2->data);
}

Por supuesto, esto no se puede usar en muchas plataformas, pero también lo son una serie de soluciones que tampoco son portátiles, dependiendo de lo que se suponga. int Talla, no paddingetc.

La mejor solución portátil (y razonablemente rápida dado un buen compilador) es el memcmp() ofrecido por @H2CO3.

Ir a un nivel de diseño más alto y usar un tipo entero lo suficientemente amplio como uint64_t en vez de struct macAcomo sugiere Kerrek SB, es muy atractivo.

Question 8

Para escribir juegos de palabras correctamente, debe usar una unión. De lo contrario, romperá las reglas estrictas de creación de alias que siguen ciertos compiladores, y el resultado será indefinido.

int EqualMac( MAC* a , MAC* b )
{
    union
    {
        MAC m ;
        uint16_t w[3] ;

    } ua , ub ;

    ua.m = *a ;
    ub.m = *b ;

    if( ua.w[0] != ub.w[0] )  
        return 0 ;

    if( ua.w[1] != ub.w[1] )
        return 0 ;

    if( ua.w[2] != ub.w[2] )
        return 0 ;

return 1 ;
}

Según C99, es seguro leer de un miembro de la unión que no es el último que se usó para almacenar un valor en él.

Si el miembro utilizado para leer el contenido de un objeto de unión no es el mismo que el último miembro utilizado para almacenar un valor en el objeto, la parte apropiada de la representación de objeto del valor se reinterpreta como una representación de objeto en el nuevo tipo como descrito en 6.2.6 (un proceso a veces llamado “tipo de juego de palabras”). Esto podría ser una representación trampa.

¿Ha sido útil esta solución?