El bitmap llena el array por posición de menor peso del byte

[MaximilianoFelice]

Al settear el primer bit de un bitarray vacío , la operación no settea el primer bit respecto a la posición de memoria, sino el bit que corresponde al peso más chico del primer byte del mismo.

Supongamos que tenemos un bitmap:
char *bitmap = malloc(2);

Nuestra memoria, en bits (8 bits por byte):
00000000 00000000

Si setteamos el primer bit obtenemos que la memoria queda con:
00000001 00000000

Cuando en realidad, esperaría obtener:
10000000 00000000

Esto, además, rompe con la interoperabilidad a otras implementaciones de bitmap.

Existe algún motivo por el que se desarrolló de esta forma, o es un bug?

[gastonprieto]

Hola,

Es el comportamiento esperado según los tests :p la verdad que no recuerdo porque lo hicimos así, y estoy casi seguro que andaba para interactuar con ext2.

Habría que analizar si era por un tema de como manejan las compus los endian o por otra cosa.

Aunque me suena razonable el cambio que propones.

[alkchofa]

Buenas, tendrá algo q ver con esto?
sisoputnfrba/foro#462

[gastonprieto]

Si, habría que fixearlo.

[MaximilianoFelice]

Confirmo lo que decís Gastón de que esto es el comportamiento esperado en EXT2. Esta documentación plantea que:

Each bit represent the current state of a block within that block group, where 1 means "used" and 0 "free/available". The first block of this block group is represented by bit 0 of byte 0, the second by bit 1 of byte 0. The 8th block is represented by bit 7 (most significant bit) of byte 0 while the 9th block is represented by bit 0 (least significant bit) of byte 1.

Si, es fija que lo hicieron así porque estaban usando las commons (?)

Hasta ahora no encontré ningún tipo de documentación que me explique si esto cambió para EXT4, o más importante aún, por qué les pintó hacerlo así. Cualquier tipo de información es bienvenida.

Por ende esto no es un bug, sino más bien un feature request. Propongo no romper la compatibilidad con el sistema de formatting anterior, sino más bien agregar una flag en algún lado que nos deje romper un poco el encapsulamiento y elegir cómo queremos almacenar los datos. Algo así como:

t_bitarray *bitarray_create(char *bitarray, size_t size, mode_t INVERSE)

¿Qué opinan?

[gastonprieto]

👍

[mgarciaisaia]

por qué les pintó hacerlo así

¿No es el viejo y conocido little-endian? Si tomás byte por byte, el bit menos significativo es el primero (el que está más a la derecha).

La joda es que nosotros estamos agregando una abstracción que te permite ver al bitarray completo en lugar de byte a byte.

+1 al flag que permita elegir uno u otro - y un poco de doc que aclare qué significa el flag.

¿Quién puede meterle mano pronto? ¿Cuánto cambian todas las funciones si tenemos que soportar las dos implementaciones?

[MaximilianoFelice]

¿No es el viejo y conocido little-endian? Si tomás byte por byte, el bit menos significativo es el primero (el que está más a la derecha).

El Endiannes es el orden en el que se van a guardar los bytes en una word. En general, Little y Big endian referencian a modelos de almacenamiento en memoria de palabras de 4 bytes, en las que, dependiendo el formato, se almacenan los bytes de forma secuencial o inversa.

No me suena que eso tenga mucho que ver con el orden de almacenamiento de bits en un bitarray, principalmente porque el primer concepto de proximidad que se me ocurre con la abstracción de Array es el espacial. Es decir, esperaría que el próximo elemento de un array sea el que se encuentra espacialmente contiguo -más aún cuando trabajamos con cosas de bajo nivel-. Admito que esto es tan solo un prejuicio mio sobre los arrays, pero no llego a comprender cuál fué la decisión de diseño que llevó a pensar que guardar la información priorizando el LSB de cada byte era una buena idea. Evidentemente se me está escapando algo, todavía no tuve mucho tiempo más que para hacer esta pregunta en StackOverflow.

¿Quién puede meterle mano pronto? ¿Cuánto cambian todas las funciones si tenemos que soportar las dos implementaciones?

Voy a tratar de verlo en estos días, estaría necesitando esto para terminar los tests de OSADA. Por el momento mi implementación está perdiendo <8 bloques por este tema, asique imagino que en cualquier momento varios grupos van a estar en la misma.

Si alguno me puede ganar de mano, se los agradecería una banda.

[MaximilianoFelice]

Bueno, me puse a buscar cuál es la intención atras de elegir estos modelos. Voy escribiendo a medida que encuentro cosas.

TL;DR: ¿Deprecamos la API actual así no cagamos la compatibilidad? ¿La pisamos directamente?

El Bit Numbering -también llamado Bit Endianness- es el sistema mediante el cual se guardan los bits en un byte. Existen varios tipos de Bit Endiannes, pero se destacan dos modelos:

• LSB n: El bit de mayor peso es el n-th bit menos significativo. Este modelo es el que usamos siempre para guardar cosas. Generalmente, n = 0.
• MSB n: El bit de mayor peso es el n-th bit más significativo. Al igual que en el modelo anterior, generalmente n = 0.

Para prácticamente todas las implementaciones, el modelo elegido es el LSB-0 y es el que que siempre estudiamos. Incluso, casi todas las implementaciones de BitArrays que encontré por ahí -como la de C#- usan LSB-0.

Como la elección del Bit Endianness es prácticamente aleatoria, existen varios protocolos que piden LSB-0 o MSB-0 casi indistintamente. Por eso, varios lenguajes proveen conversores de BitArrays para poder usar varios protocolos.

Aún tengo el problema de no haber podido encontrar un criterio de diseño por el cual la gente se inclina por uno u otro método, exceptuando algunas features de manejo de imágenes como los BMPs que tienen algo de sentido. Después, la mayoría de las cosas pasan por mantener comportamiento Legacy o cosas similares.

¿Lo bueno de todo esto?
El approach de dejar elegir que sistema de Bit Numbering usar resultaría bastante completo, y no existen motivos aparentes por los cuales cambiar el sistema traería un problema o el odio de una horda con tridentes y antorchas.

¿Lo malo?
Estamos introduciendo un breaking change, y es una fiaca. Cambiando la API de bitmap rompemos las implementaciones anteriores. Una alternativa es deprecar la API actual y eliminarla en próximas versiones.

Elegí, estoy seguro de que perderás...

[alkchofa]

Yo tenia entendido q los endiannes se usaban cuando se leia/escribía de a palabras, lo cual sería útil para dispositivos como un HD o diskettes (tengo entendido q ahora se lee de a bloques).

Fuera de eso, q tan malo/difícil sería agregar los '...' para funciones con parámetros variables y dejar por default el q ya existe?

http://stackoverflow.com/questions/2182002/convert-big-endian-to-little-endian-in-c-without-using-provided-func

[jbmild]

Buenas, yo lo que hice fue crear un bitarray_extensions.c (y su .h) en la cual puse el siguiente codigo:

#define BIT_IN_CHAR_INVERSE(bit) (0x80 >> (((bit) % CHAR_BIT)))

Luego reescribi la libreria y en lugar de usar **BIT_IN_CHAR* use BIT_IN_CHAR_INVERSE y la agregue el sufijo _inverse a cada funcion. Aparentemente me funciona bien. De momento no escribí ningún dato pero en estos días estaré probando eso.

Saludos