Jarcec’s site

Bitová pole

December 21, 2006 on 5:24 pm | In Poznámečky |

V tvorbě BitTorrent klienta jsem došel do stavu, kdy jsem potřeboval bitové pole. Nahradit ho za char nepřipadalo v úvahu, protože by to znamena enormní plýtvání místem (7 bitů by vždy šlo nazmar a to potřebuji pole, které může šahat co do velikosti až do tisíců). Proto jsem požádal JR zda-li nějaký kód nemá. Měl - ovšem ten jsem odmítl, protože se mi zdál přiliš nepřehledný (opět chyba - ale o tom až za chvíli). Proto jsem si v dnešní “vánoční hodině” programování vytvořil svůj vlastní algoritmus na práci s bitovým polem. No a postupným zjednodušováním jsem v podstatě došel ke kódu, který se v mnoha ohledech podobá tomu co stvořil JR. Ale tak aspoň vím přesně proč a jak to funguje…

Vlastní zdrojový kód:

#include

// Constant for num of bits in one byte (char)
#define TORLI_BITS_PER_BYTE 8

/* torli_bit_array_create
* Create and return bit array. Also the created array will be nullized
* @param int size - size of requested array (number of bits you need)
* @ret unsigned char * - bit array
* */
unsigned char *torli_bit_array_create(int size)
{
// modulo for unused bits in last char
int more = size % TORLI_BITS_PER_BYTE;
// if we have one, we have allocate space for them
if(more > 0) more = 1;
// This size I’m going to allocate
int alloc = (size / TORLI_BITS_PER_BYTE + more);
// Allocating sufficient space
unsigned char *ret = (unsigned char *)malloc(alloc);
// Nullize
for(more = 0; more < alloc; more++)
ret[more] = 0;
// C'est tout
return ret;
} // torli_bi_array_create(int)

/* torli_bit_array_set
* Set bit on 'position' to 'value' (only 0 or 1 are accepted)
* @param unsigned char *array - in this array
* @param int position - this bit
* @param int value - to this value (only 1 or 0)
* @ret void
* */
void torli_bit_array_set(unsigned char *array, int position, int value)
{
// Look ogly, but it's nice
(value) ? (array[position / TORLI_BITS_PER_BYTE] |= 1 << ((TORLI_BITS_PER_BYTE - 1) - position % TORLI_BITS_PER_BYTE)) : (array[position / TORLI_BITS_PER_BYTE] &= ~( 1 << ((TORLI_BITS_PER_BYTE - 1) - position % TORLI_BITS_PER_BYTE)));
// Commented because of line above - this is the same code, but code above is better
/* switch(value)
{
case 1:
array[position / 8] |= 1 << (7 - position % ;
break;
case 0:
array[position / 8] &= ~( 1 << (7 - position % );
break;
}*/
} // torli_bit_array_set(unsigned char *, int, int)

/* torli_bit_array_get
* Return value at 'position' bit in 'array' bit array. Return values are only 0 or 1.
* @param unsigned char *array - from this array
* @param int position - at this position
* @ret unsigned int - 0 or 1
* */
unsigned int torli_bit_array_get(unsigned char * array, int position)
{
// Get the byte where lays requested bit
unsigned char z = array[position / TORLI_BITS_PER_BYTE];
// By this conversion only requested bit will be safed
z = ( z << (position % TORLI_BITS_PER_BYTE) ) >> (TORLI_BITS_PER_BYTE - 1);
// C’est tout
return (unsigned int)z;
} // torli_bit_array_set(unsigned char *, int)

int main()
{
unsigned char *a = torli_bit_array_create(10);
torli_bit_array_set(a, 0, 1);
printf(”Bit c.0: %d\n”, torli_bit_array_get(a, 0));
printf(”Bit c.5: %d\n”, torli_bit_array_get(a, 9));
torli_bit_array_set(a, 9, 1);
printf(”Bit c.5: %d\n”, torli_bit_array_get(a, 9));
return 0;
}