Bit operation

Redis 2.6부터 Bit operation이 지원되었습니다.

BITOP [NOT | AND | OR | XOR ], BITCOUNT, SETBIT, GETBIT  입니다.

Bit operation에 쓰이는 자료형은 String입니다.  String이 512MB가 제한입니다.

그래서 bit offset 의 최대 길이는 0 ~ (512*1024*1024*8 -1 )입니다.

SETBIT, GETBIT, BITCOUNT, BITOP 순으로 진행하겠습니다.

우선 SETBIT는 "SETBIT key offset bitvalue(0 | 1)" 입니다.

offset이 위에서 말한 bit 범위인지, bitvalue는 맞게 들어왔는지 검사합니다.

그 후에 해당 key가 기존 DB 존재 여부를 판단하고, 없으면 String형을 생성하고

있으면 value의  Type 검사와 참조 하는 데가 있는 지를 판단해서 처리를 해줍니다.

(offset >> 3) + 1 만큼 메모리  공간을 확보한 다음에 offset >> 3에 해당하는 데이타를 가져온 후

해당 offset에 bitvalue를 set 해줍니다.

======================= Example ===========================

key user1에는 00000000 01000000 00000000이 저장되어있고
setbit user1 20 1 실행한다고 하면

(10 >> 3) + 1  크기의 메모리를 할당한후, (키가 존재하고, 이미 더 큰 메모리가 할당 되있으면 이 부분은 패스~!!)

bit = 7 - (bitoffset & 0x7); 의 동작을 하는 이유는 한 byte는 0~7의 오프셋이 있고,

사람이 이해하기 편하게 하려고 한것같습니다.(제 추측....;;)


( (uint8_t*)user1에 해당하는 value->ptr)[(10 >> 3)] 을 가져오고 또한 offset의 값을 가져옵니다. 

offset의 값을 가져오는 이유는 client에게 원래 있던 값을 리턴하기위함입니다.
그리고 가져온 바이트는 3번째 byte 00000000 을 가져오겠네요.


이젠 ( (uint8_t*)user1에 해당하는 value->ptr)[(10 >> 3)] 값에 원하는 값을 세팅할 차례입니다.

byteval &= ~(1 << bit)
offset의 비트는 0으로 나머지 비트는 그대로 둡니다.. ( offset의 값만 set해주기위해)

byteval |= ((on&0x1) << bit);
그 다음 3번째 바이트와 ((on & 0x1) << bit); 결과와 OR연산을 합니다.

( (uint8_t*)o->ptr)[byte] = byteval;  로 set을 마칩니다.

======================= Example ===========================

Bit Operation에 대해 알아보겠습니다. 단순합니다. XOR, AND, OR, NOT bit 연산을 하는데,
그 방식이 4~xx 번째 인자의 value들을 bit 연산한 결과를 3번째 인자에 저장을합니다.

4~xx 의 인자들의 value를 가리킬 포인터와(unsigned char **src),
각 value의 길이(long *len)를 저장할 변수에 값을 대입합니다.   대입하면서 maxlen과 minlen을 찾습니다.

4~xx의 인자의 갯수가 16개 이하면, 이중포문으로 각 인자들의 value들을 minlen만큼 bit 연산을 합니다.

왜 16개인지는 모르겠네요;;   이중포문이 끝나면, minlen~maxlen에 대해서 bit 연산을 합니다.

4~xx의 인자의 갯수가 16초과면 바로 아래 포문을 탑니다. 

위의 이중포문에서는 unsigned long * 4 씩 뭉탱이로하고, bit연산자별로 나뉜다음에 포문이 있는데,

아래는 포문안에 switch가있고, byte로 연산을 합니다.

위 for문에서 연산한 결과를 3번째 인자에 저장합니다. 이미 해당 key가 있다면 지우고 다시 저장합니다.

마지막으로 bitcount가 있습니다. start와 end차이(byte단위)를 구해서 해당하는 byte의 bit가 1인걸 count합니다.

이 부분에 재밌는 두가지 있습니다. (나만 그럴라나......ㅋㅋㅋ)

첫번째는 16byte씩 뭉탱뭉탱 count하는것...  CountBitsSetParallel  에 있는걸 사용했습니다.

그냥보면 그저 멍합니다. 실행해보는게 답이죠 ㅋㅋ

결과 (보기편하려고 띄어쓰기는 제가.....;; 머리가 나쁘니 ㅋㅋㅋ)
0000 1100 1100 1101 0101 1011 1010 0100
0000 1000 1000 1001 0101 0110 0101 0100
0000 0010 0010 0011 0010 0011 0010 0001
0000 0000 0000 0000 0000 0000 0000 1111
Bit Num : 15
계속하려면 아무 키나 누르십시오 . . .
와우~!! 계산기랑 수작업으로 했는데 맞게 나오네요. 당연한걸.....ㅋㅋㅋ
대충은 알겠는데 마지막은 왜 저런지;;;; 알려주세요.

두번째는 위에서 뭉탱뭉탱하고 나머지 byte들은 1byte씩 count를 하는데,
이걸 또 그냥하지 않고 256배열에 해당 index의 1의 갯수를 미리 입력해 놓았습니다.
static const unsigned char bitsinbyte[256] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,
2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,
3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,
4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아 센스쟁이....ㅋㅋㅋ

bit 연산할때 minlen, maxlen을 잘 따져서 그래도 좀 빠르게 할수도 있지않을까 생각해봅니다....