Tiago.SR - 2 months ago 5x
C Question

# Get part of specific length of allocated memory space

I have some billions of bits loaded into RAM by the use of

`malloc()`
- will call it big_set. I also have another amount of bits (will call it small_set) in RAM which are all set to 1 and I know its size (how many bits - I will call it ss_size), but can't predict it, as varies on each execution. ss_size can be sometimes as small as 100 or large as hundreds of millions.

I need to do some bitwise operations between small_set and some unpredictable parts of big_set of ss_size bits length. I can't just extend small_set with zeros on both most-significant and least-significant sides to make its size equal big_set's size, as that would be very RAM and CPU expensive (same operations will be done at same time with a lot of differently sized small_sets and also will do shift operations over small_set, expanding it would lead in much more bits to CPU work on).

Example:

big_set:
`100111001111100011000111110001100`
(would be billions of bits in reality)

small_set:
`111111`
, so ss_size is 6. (may be an unpredictable number of bits).

I need to take 6 bits length parts of big_set, e.g.:
`001100`
,
`000111`
, etc. Obs.: not necessarily Nth 6 bits, it could be from 3rd to 9th bits, for instance. I don't know how can I get it.

I don't want to get a big_set copy with everything zeroed except the 6 bits I would be taking, like on
`000000001111100000000000000000000`
, as that would be also very RAM expensive.

The question is: how can I get N bits from anywhere inside big_set, so I can do bitwise operations between they and small_set? Being N = ss_size.

I'm not sure that the example given below will give an answer to your question, also I am not sure that the realized XOR will work correctly.

But I have tried to show how confusing can be the implementation of the algorithm, if the task is to save memory.

This is my example for case of 40 bit in `big_set` and 6 bit in `small_set`:

``````#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

void setBitsInMemory(uint8_t * memPtr, size_t from, size_t to)
// sets bits in the memory allocated from memPtr (pointer to the first byte)
// where from and to are numbers of bits to be set
{
for (size_t i = from; i <= to; i++)
{
size_t block = i / 8;
size_t offset = i % 8;
*(memPtr + block) |= 0x1 << offset;
}
}

uint8_t * allocAndBuildSmallSet(size_t bitNum)
// Allocate memory to store bitNum bits and set them to 1
{
uint8_t * ptr = NULL;
size_t byteNum = 1 + bitNum / 8; // determine number of bytes for
ptr = (uint8_t*) malloc(byteNum);
if (ptr != NULL)
{
for (size_t i = 0; i < byteNum; i++) ptr[i] = 0;
setBitsInMemory(ptr, 0, bitNum - 1);
}
return ptr;
}

void printBits(uint8_t * memPtr, size_t from, size_t to)
{
for (size_t i = from; i <= to; i++)
{
size_t block = i / 8;
size_t offset = i % 8;
if (*(memPtr + block) & (0x1 << offset) )
printf("1");
else
printf("0");
}
}

void applyXOR(uint8_t * mainMem, size_t start, size_t cnt, uint8_t * pattern, size_t ptrnSize)
// Applys bitwise XOR between cnt bits of mainMem and pattern
// starting from start bit in mainMem and 0 bit in pattern
// if pattern is smaller than cnt, it will be applyed cyclically
{
size_t ptrnBlk = 0;
size_t ptrnOff = 0;
for (size_t i = start; i < start + cnt; i++)
{
size_t block = i / 8;
size_t offset = i % 8;
*(mainMem + block) ^= ((*(pattern + ptrnBlk) & (0x1 << ptrnOff)) ? 1 : 0) << offset;
ptrnOff++;
if ((ptrnBlk * 8 + ptrnOff) >= ptrnSize)
{
ptrnBlk = 0;
ptrnOff = 0;
}
if (ptrnOff % 8 == 0)
{
ptrnBlk++;
ptrnOff = 0;
}
}
}

int main(void)
{
uint8_t * big_set;
size_t ss_size;
uint8_t * small_set;
big_set = (uint8_t*)malloc(5); // 5 bytes (40 bit) without initialization
ss_size = 6;
small_set = allocAndBuildSmallSet(ss_size);
printf("Initial big_set:\n");
printBits(big_set, 0, 39);
// some operation for ss_size bits starting from 12th
applyXOR(big_set, 12, ss_size, small_set, ss_size);
// output for visual analysis
printf("\nbig_set after XOR with small_set:\n");
printBits(big_set, 0, 39);
printf("\n");
// free memory
free(big_set);
free(small_set);
}
``````

At my PC I can see the following: