2016-08-15 3 views
0

У меня есть несколько миллиардов бит, загруженных в ОЗУ, с использованием malloc() - назовем это big_set. У меня также есть другое количество бит (назовем его small_set) в ОЗУ, которые все установлены в 1, и я знаю его размер (сколько бит - я назову его ss_size), но не могу его предсказать, так как зависит от каждого исполнения. ss_size может быть как можно меньше 100 или больших, как сотни миллионов.Получить часть определенной длины выделенного пространства памяти

мне нужно сделать некоторые битовые операции между small_set и некоторых непредсказуемых частями big_set из ss_size длины бита. Я не могу просто увеличить small_set с нулями на обеих наиболее значимых и наименее значимых сторонах, чтобы сделать его размер равным Размер файла big_set, так как это было бы очень дорогостоящим ОЗУ и ЦП (одни и те же операции будут выполняться на одном и том же время с большим количеством разного размера small_set s, а также будет выполнять операции сдвига над small_set, расширяя его, чтобы больше работать на процессоре).

Пример:

big_set: 100111001111100011000111110001100 (будет миллиарды битов в реальности)

small_set: 111111, так что ss_size равно 6. (может быть непредсказуемо число битов) ,

мне нужно взять 6 бит части длины big_set, например .: 001100, 000111 и т.д. Obs .: не обязательно NTH 6 бит, это может быть от 3 до 9-бит, например. Я не знаю, как это получить.

Я не хочу, чтобы получить big_set копию со всем обнуленным кроме 6 битых I будет принимать, как на 000000001111100000000000000000000, поскольку это было бы очень дорого RAM.

Возникает вопрос: как я могу получить N битов из любой точки внутри big_set, так что я могу сделать битовые операции между они и small_set? Будучи N = ss_size.

+0

И вопрос является? – alk

+0

Я вижу, что проблема не в хранении 'small_set' в памяти, а в реализации требуемой операции (побитовые операции между' small_set' и 'big_set'). Вы уже пишете код для OR, AND, XOR и других операций? – VolAnd

+0

@VolAnd У меня уже есть большинство необходимых поразрядных операций, но в то время, когда я их писал, я расширил «small_set» с нулями с обеих сторон, чтобы размер его был равен размеру 'big_set'. Я только заметил, что это не очень хорошая идея из-за большого использования ОЗУ, и теперь я хочу изменить его, как описано в сообщении вопроса. –

ответ

1

Я не уверен, что приведенный ниже пример даст ответ на ваш вопрос, также я не уверен, что реализованный XOR будет работать правильно.

Но я попытался показать, насколько запутанной может быть реализация алгоритма, если задача заключается в сохранении памяти.

Это мой пример для случая 40 бит в big_set и 6 бит в 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); 
} 

На моем компьютере я вижу следующее:

enter image description here

 Смежные вопросы

  • Нет связанных вопросов^_^