bitops.c/redisPopcount: optimization in loop

### This new redisPopcount reduce the execution time by 10% than the old one.
+ The old version counts 16 bytes in a loop. 
Every loop it adds the pop(uint32_t) to the highest byte of a uint32_t, then shift 24 and add the 4 uint32_t. 
We can add all the 4 pop(uint32_t) to a highest byte of a uint32_t and shift 24.
This will cause 5% reduce.

+ The ceil of a byte is 255, and the ceil of pop(a byte) is 8
floor(255 / 8) = 31;
floor(31 / 4) = 7;
So we can count 7*4=28 bytes in a loop.
This will cause %5 reduce.

#### The test for short length is not stable, because loop will cause great influence.

#### benchmark for execution time.
Start:
length: 128
New version speed up 1.75%
New New version speed up 6.26%
length: 256
New version speed up 11.11%
New New version speed up 17.33%
length: 512
New version speed up 7.67%
New New version speed up 10.23%
length: 1024
New version speed up 4.04%
New New version speed up 10.79%
length: 2048
New version speed up 6.35%
New New version speed up 11.98%
length: 4096
New version speed up 6.22%
New New version speed up 11.61%
length: 8192
New version speed up 5.74%
New New version speed up 11.03%
length: 16384
New version speed up 6.02%
New New version speed up 11.44%
length: 32768
New version speed up 5.74%
New New version speed up 11.28%
length: 65536
New version speed up 5.71%
New New version speed up 11.36%
length: 131072
New version speed up 5.73%
New New version speed up 11.40%
length: 262144
New version speed up 5.79%
New New version speed up 11.44%
length: 524288
New version speed up 5.74%
New New version speed up 11.44%
length: 1048576
New version speed up 5.69%
New New version speed up 11.41%
length: 2097152
New version speed up 5.69%
New New version speed up 11.46%
length: 4194304
New version speed up 5.72%
New New version speed up 11.43%
length: 8388608
New version speed up 5.70%
New New version speed up 11.40%
.
.
.
*****
## TEST CODE
    #include <stdio.h>
    #include <inttypes.h>
    #include <sys/time.h>
    
    size_t newnewRedisPopcount(void *s, long count) {
        size_t bits = 0;
        unsigned char *p = s;
        uint32_t *p4;
        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};
    
        /* Count initial bytes not aligned to 32 bit. */
        while((unsigned long)p & 3 && count) {
            bits += bitsinbyte[*p++];
            count--;
        }
    
        /* Count bits 28 bytes at a time */
        p4 = (uint32_t*)p;
        while(count>=28) {
            uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;
    
            aux1 = *p4++;
            aux2 = *p4++;
            aux3 = *p4++;
            aux4 = *p4++;
            aux5 = *p4++;
            aux6 = *p4++;
            aux7 = *p4++;
            count -= 28;
    
            aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
            aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
            aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
            aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
            aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
            aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
            aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
            aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
            aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
            aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
            aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
            aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
            aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
            aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
            bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
                        ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
                        ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
                        ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
                        ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) +
                        ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
                        ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
        }
        /* Count the remaining bytes. */
        p = (unsigned char*)p4;
        while(count--) bits += bitsinbyte[*p++];
        return bits;
    }
    size_t newRedisPopcount(void *s, long count) {
        size_t bits = 0;
        unsigned char *p = s;
        uint32_t *p4;
        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};
    
        /* Count initial bytes not aligned to 32 bit. */
        while((unsigned long)p & 3 && count) {
            bits += bitsinbyte[*p++];
            count--;
        }
    
        /* Count bits 16 bytes at a time */
        p4 = (uint32_t*)p;
        while(count>=16) {
            uint32_t aux1, aux2, aux3, aux4;
    
            aux1 = *p4++;
            aux2 = *p4++;
            aux3 = *p4++;
            aux4 = *p4++;
            count -= 16;
    
            aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
            aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
            aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
            aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
            aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
            aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
            aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
            aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
            bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
                        ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
                        ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
                        ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
        }
        /* Count the remaining bytes. */
        p = (unsigned char*)p4;
        while(count--) bits += bitsinbyte[*p++];
        return bits;
    }
    
    size_t redisPopcount(void *s, long count) {
        size_t bits = 0;
        unsigned char *p = s;
        uint32_t *p4;
        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};
    
        /* Count initial bytes not aligned to 32 bit. */
        while((unsigned long)p & 3 && count) {
            bits += bitsinbyte[*p++];
            count--;
        }
    
        /* Count bits 16 bytes at a time */
        p4 = (uint32_t*)p;
        while(count>=16) {
            uint32_t aux1, aux2, aux3, aux4;
    
            aux1 = *p4++;
            aux2 = *p4++;
            aux3 = *p4++;
            aux4 = *p4++;
            count -= 16;
    
            aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
            aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
            aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
            aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
            aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
            aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
            aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
            aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
            bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
        }
        /* Count the remaining bytes. */
        p = (unsigned char*)p4;
        while(count--) bits += bitsinbyte[*p++];
        return bits;
    }
    
    long long ustime(void) {
        struct timeval tv;
        long long ust;
    
        gettimeofday(&tv, NULL);
        ust = ((long long)tv.tv_sec) * 1000000;
        ust += tv.tv_usec;
        return ust;
    }
    
    char tmp[1<<29];
    
    void initialize()
    {
        int i;
        for (i = 0; i < 1<<29; i++)
            tmp[i] = rand();
    }
    void runTest(int length)
    {
        int i;
        long long timePre, timeCur;
        size_t res1, res2, res3;
        long long timePreTotal, timeNewTotal, timeNewNewTotal;
        timePreTotal = timeNewTotal = timeNewNewTotal = 0;
        for (i = 0; i < 4096; i++) {
            int start;
            start = rand() % sizeof(tmp - length);
    
            timePre = ustime();
            res1 = redisPopcount(start + tmp, length);
            timeCur = ustime();
            timePreTotal += timeCur - timePre;
    
            timePre = ustime();
            res2 = newRedisPopcount(start + tmp, length);
            timeCur = ustime();
            timeNewTotal += timeCur - timePre;
    
            timePre = ustime();
            res3 = newnewRedisPopcount(start + tmp, length);
            timeCur = ustime();
            timeNewNewTotal += timeCur - timePre;
    
            if (res1 != res2 || res2 != res3)
                printf("Panic!\n");
        }
        /*printf("Old version time: %lld\n", timePreTotal);*/
        /*printf("New version time: %lld\n", timeNewTotal);*/
        /*printf("New New version time: %lld\n", timeNewNewTotal);*/
    
        printf("length: %d\n", length);
        printf("New version speed up %.2lf%%\n", 100.0*(timePreTotal - timeNewTotal)/timePreTotal);
        printf("New New version speed up %.2lf%%\n", 100.0*(timePreTotal - timeNewNewTotal)/timePreTotal);
    }
    int main(int argc, char *argv[])
    {
        int i;
        initialize();
        printf("Start:\n");
        for(i = 128; i < 1<<29; i <<= 1)
            runTest(i);
        return 0;
    }