La forma más eficiente de crear una matriz bool en C - AVR

Estoy usando un Atmega32 para leer varios sensores usando su ADC.

Usando lógica digital y algunos multiplexores, multiplexé la totalidad de PORTA, usando PA0:6 para la dirección y PA7 como entrada. Por lo tanto, puedo tener un máximo de 128 entradas desde un solo PUERTO.

Ahora, dado que el usuario operará el sistema a través de una computadora (usando RS232), será posible agregar o eliminar sensores, por lo que el sistema debe realizar un seguimiento de qué direcciones están libres para agregar sensores y de qué direcciones leer.

Estaba pensando en usar una matriz booleana de 128 bits como banderas para indicar si hay un sensor en una dirección determinada.

Si bien C no tiene soporte nativo para variables de un solo bit, es posible usar campos de bits para agrupar hasta 8 "variables booleanas" en un solo carácter sin firmar.

Entonces, he creado la siguiente estructura:

typedef struct bool_s{
      uint8_t bit1:1;
}bool_t;

Luego, creé una matriz de tipo bool_t con un tamaño de 128, con la esperanza de que todo estuviera bien empaquetado, pero sizeof()me dice que el tamaño de la matriz es de 128 bytes en lugar de los 16 bytes que esperaba.

Técnicamente, podría crear una sola estructura con 128 variables de 1 bit:

typedef struct Flag_s{
      uint8_t F1:1;
      uint8_t F2:1;
      uint8_t F3:1;
      [...]
      uint8_t F128:1;
}Flag_t;

El problema con este enfoque es que si bien reduce el uso de memoria, no es muy práctico de usar y ocupa demasiado espacio en el código.

¿Hay alguna manera fácil de crear una gran cantidad de banderas o estoy pidiendo demasiado? Quiero decir, no es que ahorrar 112 bytes vaya a hacer una gran diferencia cuando tienes 2K disponibles, pero ¿y si necesito aún más banderas?

¿No debería estar esto en Stack Overflow...?
@Joshpbarron Esto es específico para C incrustado, las variables booleanas existen en C99 y, además, no es como usar algunos bytes adicionales aquí y allá, hará una diferencia significativa cuando tenga GiB de memoria disponible, y si dijera que estaba usando microcontroladores, probablemente me dirían que fuera al intercambio de pilas EE.

Respuestas (3)

Los campos de bits no funcionan así. La respuesta de Cventu muestra una forma correcta de usarlos, pero en este caso, recomiendo evitarlos por completo.

En su lugar, cree una matriz de valores de 8 bits y use desplazamiento y enmascaramiento para acceder a ella:

uint8_t flags[16];

//Initialize the flags
void init_flags(void)
{
    for (i = 0; i < 16; i++)
    {
        flags[i] = 0x00;
    }
}

//Set one flag based on the address
void set_flag(uint8_t address)
{
    flags[address/8] |= 0x1 << (address % 8);
}

//Clear one flag based on the address
void clear_flag(uint8_t address)
{
    flags[address/8] &= ~(0x1 << (address % 8));
}

//Check whether a flag is set
bool get_flag_state(uint8_t address)
{
    return (flags[address/8] & (0x1 << (address % 0x8))) != 0x00;
}

Esto es probablemente lo que hará el compilador con los accesos de campo de bits de todos modos, y es más fácil trabajar con él. Algunos optimizadores son malos para optimizar campos de bits, por lo que el compilador podría incluso hacerlo peor. Todos los compiladores que he visto convierten la división y el módulo por una potencia constante de dos en instrucciones de desplazamiento a la derecha y AND. Puede usar esas operaciones directamente si se siente paranoico:

flags[address>>3] |= 0x1 << (address & 0x7);

Los campos de bits se parecen más a estructuras que a matrices. En mi experiencia, solo son útiles para cosas que tienen nombres, como campos de registro.

En procesadores más avanzados (como x86), los campos de bits generalmente se implementan utilizando variables elementales aún más grandes, como uint32_t. Pero la idea es la misma: bit a bit OR se usa para establecer las banderas, bit a bit NOT+AND se usa para borrar las banderas, y bit a bit AND se usa para verificar las banderas, con la máscara generada usando el <<operador o definida como constantes con macros
Vine aquí para decir github.com/vonj/snippets/blob/master/bitarray.c pero me ganaste. :)
Esa es una aritmética costosa (dividir y modificar) para micros de baja potencia.
Si bien su código es más genérico, algunas MCU (por ejemplo, PIC18) tienen la capacidad de leer/establecer bits individuales en la RAM directamente. Esto reduciría mucho la carga. Uno puede verificar esto, ya que los compiladores no siempre reconocen lo que está haciendo allí.
Las potencias de dos de @JohnU son bastante baratas para hacer div y mod, % 8 es lo mismo obtener los 3 bits más bajos (& 0x07) y /8 se puede hacer con un bitshift (>> 0x03)
Sí, los compiladores modernos a menudo podrán reemplazar el div/mod con shr/y para divisores que son potencias de dos
Esto es simplemente perfecto: memoria eficiente, portátil y fácil de usar. Gracias, realmente aprecio tu ayuda!
@JohnU Nunca he visto que la división o la división del módulo por una potencia constante de dos se compilen en otra cosa que no sean las instrucciones shift y AND. Pero definitivamente no quieres dividir o modificar por una variable.
La razón por la que los campos de bits no funcionan así es porque cada elemento de una matriz debe tener una dirección y ser compatible con la aritmética de punteros, lo que impide que un elemento ocupe menos del tamaño de char (es decir, un byte). Múltiples campos de bits dentro de una estructura pueden "compartir" un byte, pero no hay tanta suerte con los elementos de la matriz.
@Gorloth: cierto, ¿por qué no escribirlo de esa manera en primer lugar en lugar de esperar que el compilador lo cambie?
@JohnU Porque debe esforzarse por escribir el código más legible posible. Simplemente haga eso, luego desensamble el código y vea cómo terminó. Solo debe optimizar manualmente el código si descubre que el compilador está roto y no reemplazó la división por turnos (dado que las optimizaciones están habilitadas en primer lugar). En cuyo caso, debe comentar por qué realizó optimizaciones manuales y también presentar un informe de errores al proveedor del compilador.

Suena un poco confuso, pero tal vez algo como esto pueda ayudar:

struct bits_field {
                       unsigned char bit_7 :1;
                       unsigned char bit_6 :1;
                       unsigned char bit_5 :1;
                       unsigned char bit_4 :1;
                       unsigned char bit_3 :1;
                       unsigned char bit_2 :1;
                       unsigned char bit_1 :1;
                       unsigned char bit_0 :1;

                   };

union dt {
             struct bits_field a;
             unsigned char b;
         };

Después de definirlos, declare la siguiente variable:

union dt my_data;

Podrá escribir un grupo completo de ocho bits juntos usando: my_data.b

O puede escribir cada bit individualmente usando: my_data.a.bit_7 (o 6,5,4,3,2,1,0)

En caso de que funcione para usted, replique esto 16 veces (usando una matriz o estructura) y podrá manejar 128 bits individualmente.

¡Háganos saber si funcionó! Buena suerte

También pensé en usar una estructura con 8 variables de 1 bit, pero luego tendría que escribir algún tipo de función para traducir el número de dirección en algo que pudiera usar con tal matriz, lo que solo agregaría confusión y sobrecarga. Ah, y por cierto, finalmente alguien me mostró un buen ejemplo de cómo el tipo de datos de unión puede ser útil. :PAG
El principal problema aquí es que los campos de bits pueden contener cualquier cantidad de bits y bytes de relleno, una de las muchas cosas que los hacen poco confiables y no portátiles. Un sindicato no soluciona eso.

Cree una estructura en la que declare banderas de ocho bits que terminen siendo un byte. Luego cree una matriz de estas estructuras de 8 bits.