Encontrar la posición de '1 de manera eficiente en una matriz de bits

Question

Estoy cableando un programa que prueba un conjunto de cables para circuitos abiertos o cortocircuitos. El programa, que se ejecuta en un AVR, conduce un vector de prueba (una caminata '1') a los cables y recibe el resultado de nuevo. Compara este vector resultante con los datos esperados que ya están almacenados en una tarjeta SD o EEPROM externa.

Aquí hay un ejemplo, supongamos que tenemos un conjunto de 8 cables, todos los cuales son directos, es decir, no tienen uniones. Entonces, si manejamos 0b00000010 deberíamos recibir 0b00000010.

Supongamos que recibimos 0b11000010. Esto implica que hay un cortocircuito entre el cable 7,8 y el cable 2. Puedo detectar qué bits me interesan por 0b00000010^0b11000010 = 0b11000000. Esto me dice claramente que los cables 7 y 8 son los culpables, pero ¿cómo puedo encontrar la posición de estos '1 de manera eficiente en una matriz de bits grande? Es fácil hacer esto solo por 8 cables con máscaras de bits, pero el sistema que estoy desarrollando debe manejar hasta 300 hilos (bits). Antes de comenzar a usar macros como los siguientes y probar cada bit en una matriz de 300 * 300 bits, quería preguntar si había una solución más elegante.

#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) 

Solo para mostrar mejor cómo detectar un circuito abierto. Datos esperados: 0b00000010, datos recibidos: 0b00000000 (el cable no se tira demasiado). 0b00000010^0b00000000 = 0b0b00000010 - el cable 2 está abierto.

NOTA: Sé que probar 300 cables no es algo que la pequeña RAM dentro de un AVR Mega 1281 pueda manejar, es por eso que dividiré esto en grupos, es decir, probaré 50 cables, compararé, mostraré resultados y luego avanzaré.

Answer 1

Muchas arquitecturas proporcionan instrucciones específicas para ubicar el primer bit configurado en una palabra, o para contar el número de bits establecidos. Los compiladores generalmente proporcionan intrínsecos para estas operaciones, por lo que no es necesario que escriba el ensamblaje en línea. GCC, por ejemplo, proporciona __builtin_ffs, __builtin_ctz, __builtin_popcount, etc., cada uno de los cuales debe asignarse a la instrucción adecuada en la arquitectura de destino, explotando el paralelismo de nivel de bit.

Si la arquitectura de destino no los admite, el compilador emite una implementación de software eficiente. El enfoque ingenuo de probar el vector bit a bit en el software no es muy eficiente.

Si su compilador no implementa esto, aún puede codificar su propia implementación usando un de Bruijn sequence.

Answer 2

Puede usar una tabla de búsqueda. Por ejemplo log-base-2 búsqueda en la tabla de 255 bytes puede ser usado para encontrar el más significativo de 1 bit en un byte:

uint8_t bit1 = log2[bit_mask]; 

donde log2 se define como sigue:

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 */ 
    ... 
} 

En la mayoría de los procesadores una tabla de búsqueda como esta irá a la ROM. Pero AVR es una máquina de Harvard y para colocar datos en el espacio de código (ROM) se requiere una extensión especial no estándar, que depende del compilador. Por ejemplo, el compilador IAR AVR necesitaría usar la palabra clave extendida __flash. En WinAVR (AVR GNU) necesitaría usar el atributo PROGMEM, pero es más complejo que eso, porque también necesitaría usar macros especiales para leer desde el espacio del programa.

Answer 3

¿Con qué frecuencia espera fallas? Si no los espera tan a menudo, parece inútil optimizar el caso de "falla": la única parte que realmente importará para la velocidad es el caso "sin culpa".

Para optimizar el caso sin culpa, simplemente XOR el resultado real con el resultado esperado y una prueba input^expected == 0 para ver si se han establecido algunos bits.

Puede utilizar una estrategia similar para optimizar el caso de "pocos fallos", si además espera que el número de fallas sea típicamente pequeño cuando existen - enmascare el valor input^expected para obtener solo los primeros 8 bits, solo los segundos 8 bits, y así sucesivamente, y comparar cada uno de esos resultados a cero. Luego, solo necesita buscar los bits establecidos dentro de los que no son iguales a cero, lo que debería limitar el espacio de búsqueda a algo que se pueda hacer bastante rápido.

Answer 4

creo que sólo hay una manera de hacer esto:

• crear una matriz a cabo "OutData". Cada elemento de la matriz puede, por ejemplo, corresponder a un registro de puerto de 8 bits.
• Envíe la fecha de salida de los cables.
• Vuelve a leer esta información como "indata".
• Almacene los indata en una matriz asignada exactamente como los outdata.
• En un ciclo, XOR cada byte de outdata con cada byte de indata.

---

no te recomiendo funciones en línea en lugar de los macros.

¿Por qué su MCU no puede manejar 300 hilos?

300/8 = 37.5 bytes. Redondeado a 38. Necesita ser almacenado dos veces, outdata e indata, 38 * 2 = 76 bytes.

No puede ahorrar 76 bytes de RAM?

Answer 5

Creo que te estás perdiendo el bosque a través de los árboles. Parece una prueba de cama de uñas. Primero pruebe algunas suposiciones: 1) Usted sabe qué clavijas deben estar activas para cada clavija probada/energizada. 2) tiene una netlist traducida para el paso 1 en un archivo en sd

Si opera en un nivel de byte así como en un bit, simplifica el problema. Si energiza un pin, se almacena un patrón esperado en su archivo. Primero busca los bytes no coincidentes; identificar los pines no coincidentes en el byte; Finalmente, almacene el pin energizado con los números de pin defectuosos.

No necesita una matriz para buscar o resultados. idea general:

numwires=300; 

numbytes=numwires/8 + (numwires%8)?1:0; 

for(unsigned char currbyte=0; currbyte<numbytes; currbyte++) 
{ 
    unsigned char testbyte=inchar(baseaddr+currbyte) 
    unsigned char goodbyte=getgoodbyte(testpin,currbyte/*byte offset*/); 
    if(testbyte^goodbyte){ 
    // have a mismatch report the pins 
    for(j=0, mask=0x01; mask<0x80;mask<<=1, j++){ 
     if((mask & testbyte) != (mask & goodbyte)) // for clarity 
      logbadpin(testpin, currbyte*8+j/*pin/wirevalue*/, mask & testbyte /*bad value*/); 

    } 

}