Return the position of the first bit set to one (if 'bit' is 1) or * zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes. * * The function is guaranteed to return a value >= 0 if 'bit' is 0 since if * no zero bit is found, it returns count*8 assuming the string is zero * padded on the right. However if 'bit' is 1 it is possible that there is * not a single set bit in th
| 99 | * padded on the right. However if 'bit' is 1 it is possible that there is |
| 100 | * not a single set bit in the bitmap. In this special case -1 is returned. */ |
| 101 | long long redisBitpos(void *s, unsigned long count, int bit) { |
| 102 | unsigned long *l; |
| 103 | unsigned char *c; |
| 104 | unsigned long skipval, word = 0, one; |
| 105 | long long pos = 0; /* Position of bit, to return to the caller. */ |
| 106 | unsigned long j; |
| 107 | int found; |
| 108 | |
| 109 | /* Process whole words first, seeking for first word that is not |
| 110 | * all ones or all zeros respectively if we are looking for zeros |
| 111 | * or ones. This is much faster with large strings having contiguous |
| 112 | * blocks of 1 or 0 bits compared to the vanilla bit per bit processing. |
| 113 | * |
| 114 | * Note that if we start from an address that is not aligned |
| 115 | * to sizeof(unsigned long) we consume it byte by byte until it is |
| 116 | * aligned. */ |
| 117 | |
| 118 | /* Skip initial bits not aligned to sizeof(unsigned long) byte by byte. */ |
| 119 | skipval = bit ? 0 : UCHAR_MAX; |
| 120 | c = (unsigned char*) s; |
| 121 | found = 0; |
| 122 | while((unsigned long)c & (sizeof(*l)-1) && count) { |
| 123 | if (*c != skipval) { |
| 124 | found = 1; |
| 125 | break; |
| 126 | } |
| 127 | c++; |
| 128 | count--; |
| 129 | pos += 8; |
| 130 | } |
| 131 | |
| 132 | /* Skip bits with full word step. */ |
| 133 | l = (unsigned long*) c; |
| 134 | if (!found) { |
| 135 | skipval = bit ? 0 : ULONG_MAX; |
| 136 | while (count >= sizeof(*l)) { |
| 137 | if (*l != skipval) break; |
| 138 | l++; |
| 139 | count -= sizeof(*l); |
| 140 | pos += sizeof(*l)*8; |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | /* Load bytes into "word" considering the first byte as the most significant |
| 145 | * (we basically consider it as written in big endian, since we consider the |
| 146 | * string as a set of bits from left to right, with the first bit at position |
| 147 | * zero. |
| 148 | * |
| 149 | * Note that the loading is designed to work even when the bytes left |
| 150 | * (count) are less than a full word. We pad it with zero on the right. */ |
| 151 | c = (unsigned char*)l; |
| 152 | for (j = 0; j < sizeof(*l); j++) { |
| 153 | word <<= 8; |
| 154 | if (count) { |
| 155 | word |= *c; |
| 156 | c++; |
| 157 | count--; |
| 158 | } |