Count number of bits set in the binary array pointed by 's' and long * 'count' bytes. The implementation of this function is required to * work with an input string length up to 512 MB or more (server.proto_max_bulk_len) */
| 38 | * 'count' bytes. The implementation of this function is required to |
| 39 | * work with an input string length up to 512 MB or more (server.proto_max_bulk_len) */ |
| 40 | long long redisPopcount(void *s, long count) { |
| 41 | long long bits = 0; |
| 42 | unsigned char *p = s; |
| 43 | uint32_t *p4; |
| 44 | 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}; |
| 45 | |
| 46 | /* Count initial bytes not aligned to 32 bit. */ |
| 47 | while((unsigned long)p & 3 && count) { |
| 48 | bits += bitsinbyte[*p++]; |
| 49 | count--; |
| 50 | } |
| 51 | |
| 52 | /* Count bits 28 bytes at a time */ |
| 53 | p4 = (uint32_t*)p; |
| 54 | while(count>=28) { |
| 55 | uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7; |
| 56 | |
| 57 | aux1 = *p4++; |
| 58 | aux2 = *p4++; |
| 59 | aux3 = *p4++; |
| 60 | aux4 = *p4++; |
| 61 | aux5 = *p4++; |
| 62 | aux6 = *p4++; |
| 63 | aux7 = *p4++; |
| 64 | count -= 28; |
| 65 | |
| 66 | aux1 = aux1 - ((aux1 >> 1) & 0x55555555); |
| 67 | aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333); |
| 68 | aux2 = aux2 - ((aux2 >> 1) & 0x55555555); |
| 69 | aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333); |
| 70 | aux3 = aux3 - ((aux3 >> 1) & 0x55555555); |
| 71 | aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333); |
| 72 | aux4 = aux4 - ((aux4 >> 1) & 0x55555555); |
| 73 | aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333); |
| 74 | aux5 = aux5 - ((aux5 >> 1) & 0x55555555); |
| 75 | aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333); |
| 76 | aux6 = aux6 - ((aux6 >> 1) & 0x55555555); |
| 77 | aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333); |
| 78 | aux7 = aux7 - ((aux7 >> 1) & 0x55555555); |
| 79 | aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333); |
| 80 | bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) + |
| 81 | ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) + |
| 82 | ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) + |
| 83 | ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) + |
| 84 | ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) + |
| 85 | ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) + |
| 86 | ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24; |
| 87 | } |
| 88 | /* Count the remaining bytes. */ |
| 89 | p = (unsigned char*)p4; |
| 90 | while(count--) bits += bitsinbyte[*p++]; |
| 91 | return bits; |
| 92 | } |
| 93 | |
| 94 | /* Return the position of the first bit set to one (if 'bit' is 1) or |
| 95 | * zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes. |