关键词搜索

源码搜索 ×
×

漫话Redis源码之七十七

发布2022-02-13浏览510次

详情内容

这里主要讲位域操作,大家要对基本的位操作有深刻的理解:

  1. /* The following set.*Bitfield and get.*Bitfield functions implement setting
  2. * and getting arbitrary size (up to 64 bits) signed and unsigned integers
  3. * at arbitrary positions into a bitmap.
  4. *
  5. * The representation considers the bitmap as having the bit number 0 to be
  6. * the most significant bit of the first byte, and so forth, so for example
  7. * setting a 5 bits unsigned integer to value 23 at offset 7 into a bitmap
  8. * previously set to all zeroes, will produce the following representation:
  9. *
  10. * +--------+--------+
  11. * |00000001|01110000|
  12. * +--------+--------+
  13. *
  14. * When offsets and integer sizes are aligned to bytes boundaries, this is the
  15. * same as big endian, however when such alignment does not exist, its important
  16. * to also understand how the bits inside a byte are ordered.
  17. *
  18. * Note that this format follows the same convention as SETBIT and related
  19. * commands.
  20. */
  21. void setUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, uint64_t value) {
  22. uint64_t byte, bit, byteval, bitval, j;
  23. for (j = 0; j < bits; j++) {
  24. bitval = (value & ((uint64_t)1<<(bits-1-j))) != 0;
  25. byte = offset >> 3;
  26. bit = 7 - (offset & 0x7);
  27. byteval = p[byte];
  28. byteval &= ~(1 << bit);
  29. byteval |= bitval << bit;
  30. p[byte] = byteval & 0xff;
  31. offset++;
  32. }
  33. }
  34. void setSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, int64_t value) {
  35. uint64_t uv = value; /* Casting will add UINT64_MAX + 1 if v is negative. */
  36. setUnsignedBitfield(p,offset,bits,uv);
  37. }
  38. uint64_t getUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
  39. uint64_t byte, bit, byteval, bitval, j, value = 0;
  40. for (j = 0; j < bits; j++) {
  41. byte = offset >> 3;
  42. bit = 7 - (offset & 0x7);
  43. byteval = p[byte];
  44. bitval = (byteval >> bit) & 1;
  45. value = (value<<1) | bitval;
  46. offset++;
  47. }
  48. return value;
  49. }
  50. int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
  51. int64_t value;
  52. union {uint64_t u; int64_t i;} conv;
  53. /* Converting from unsigned to signed is undefined when the value does
  54. * not fit, however here we assume two's complement and the original value
  55. * was obtained from signed -> unsigned conversion, so we'll find the
  56. * most significant bit set if the original value was negative.
  57. *
  58. * Note that two's complement is mandatory for exact-width types
  59. * according to the C99 standard. */
  60. conv.u = getUnsignedBitfield(p,offset,bits);
  61. value = conv.i;
  62. /* If the top significant bit is 1, propagate it to all the
  63. * higher bits for two's complement representation of signed
  64. * integers. */
  65. if (bits < 64 && (value & ((uint64_t)1 << (bits-1))))
  66. value |= ((uint64_t)-1) << bits;
  67. return value;
  68. }
  69. /* The following two functions detect overflow of a value in the context
  70. * of storing it as an unsigned or signed integer with the specified
  71. * number of bits. The functions both take the value and a possible increment.
  72. * If no overflow could happen and the value+increment fit inside the limits,
  73. * then zero is returned, otherwise in case of overflow, 1 is returned,
  74. * otherwise in case of underflow, -1 is returned.
  75. *
  76. * When non-zero is returned (overflow or underflow), if not NULL, *limit is
  77. * set to the value the operation should result when an overflow happens,
  78. * depending on the specified overflow semantics:
  79. *
  80. * For BFOVERFLOW_SAT if 1 is returned, *limit it is set maximum value that
  81. * you can store in that integer. when -1 is returned, *limit is set to the
  82. * minimum value that an integer of that size can represent.
  83. *
  84. * For BFOVERFLOW_WRAP *limit is set by performing the operation in order to
  85. * "wrap" around towards zero for unsigned integers, or towards the most
  86. * negative number that is possible to represent for signed integers. */
  87. #define BFOVERFLOW_WRAP 0
  88. #define BFOVERFLOW_SAT 1
  89. #define BFOVERFLOW_FAIL 2 /* Used by the BITFIELD command implementation. */
  90. int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) {
  91. uint64_t max = (bits == 64) ? UINT64_MAX : (((uint64_t)1<<bits)-1);
  92. int64_t maxincr = max-value;
  93. int64_t minincr = -value;
  94. if (value > max || (incr > 0 && incr > maxincr)) {
  95. if (limit) {
  96. if (owtype == BFOVERFLOW_WRAP) {
  97. goto handle_wrap;
  98. } else if (owtype == BFOVERFLOW_SAT) {
  99. *limit = max;
  100. }
  101. }
  102. return 1;
  103. } else if (incr < 0 && incr < minincr) {
  104. if (limit) {
  105. if (owtype == BFOVERFLOW_WRAP) {
  106. goto handle_wrap;
  107. } else if (owtype == BFOVERFLOW_SAT) {
  108. *limit = 0;
  109. }
  110. }
  111. return -1;
  112. }
  113. return 0;
  114. handle_wrap:
  115. {
  116. uint64_t mask = ((uint64_t)-1) << bits;
  117. uint64_t res = value+incr;
  118. res &= ~mask;
  119. *limit = res;
  120. }
  121. return 1;
  122. }
  123. int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) {
  124. int64_t max = (bits == 64) ? INT64_MAX : (((int64_t)1<<(bits-1))-1);
  125. int64_t min = (-max)-1;
  126. /* Note that maxincr and minincr could overflow, but we use the values
  127. * only after checking 'value' range, so when we use it no overflow
  128. * happens. */
  129. int64_t maxincr = max-value;
  130. int64_t minincr = min-value;
  131. if (value > max || (bits != 64 && incr > maxincr) || (value >= 0 && incr > 0 && incr > maxincr))
  132. {
  133. if (limit) {
  134. if (owtype == BFOVERFLOW_WRAP) {
  135. goto handle_wrap;
  136. } else if (owtype == BFOVERFLOW_SAT) {
  137. *limit = max;
  138. }
  139. }
  140. return 1;
  141. } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) {
  142. if (limit) {
  143. if (owtype == BFOVERFLOW_WRAP) {
  144. goto handle_wrap;
  145. } else if (owtype == BFOVERFLOW_SAT) {
  146. *limit = min;
  147. }
  148. }
  149. return -1;
  150. }
  151. return 0;
  152. handle_wrap:
  153. {
  154. uint64_t msb = (uint64_t)1 << (bits-1);
  155. uint64_t a = value, b = incr, c;
  156. c = a+b; /* Perform addition as unsigned so that's defined. */
  157. /* If the sign bit is set, propagate to all the higher order
  158. * bits, to cap the negative value. If it's clear, mask to
  159. * the positive integer limit. */
  160. if (bits < 64) {
  161. uint64_t mask = ((uint64_t)-1) << bits;
  162. if (c & msb) {
  163. c |= mask;
  164. } else {
  165. c &= ~mask;
  166. }
  167. }
  168. *limit = c;
  169. }
  170. return 1;
  171. }
  172. /* Debugging function. Just show bits in the specified bitmap. Not used
  173. * but here for not having to rewrite it when debugging is needed. */
  174. void printBits(unsigned char *p, unsigned long count) {
  175. unsigned long j, i, byte;
  176. for (j = 0; j < count; j++) {
  177. byte = p[j];
  178. for (i = 0x80; i > 0; i /= 2)
  179. printf("%c", (byte & i) ? '1' : '0');
  180. printf("|");
  181. }
  182. printf("\n");
  183. }
  184. /* -----------------------------------------------------------------------------
  185. * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
  186. * -------------------------------------------------------------------------- */
  187. #define BITOP_AND 0
  188. #define BITOP_OR 1
  189. #define BITOP_XOR 2
  190. #define BITOP_NOT 3
  191. #define BITFIELDOP_GET 0
  192. #define BITFIELDOP_SET 1
  193. #define BITFIELDOP_INCRBY 2
  194. /* This helper function used by GETBIT / SETBIT parses the bit offset argument
  195. * making sure an error is returned if it is negative or if it overflows
  196. * Redis 512 MB limit for the string value or more (server.proto_max_bulk_len).
  197. *
  198. * If the 'hash' argument is true, and 'bits is positive, then the command
  199. * will also parse bit offsets prefixed by "#". In such a case the offset
  200. * is multiplied by 'bits'. This is useful for the BITFIELD command. */
  201. int getBitOffsetFromArgument(client *c, robj *o, uint64_t *offset, int hash, int bits) {
  202. long long loffset;
  203. char *err = "bit offset is not an integer or out of range";
  204. char *p = o->ptr;
  205. size_t plen = sdslen(p);
  206. int usehash = 0;
  207. /* Handle #<offset> form. */
  208. if (p[0] == '#' && hash && bits > 0) usehash = 1;
  209. if (string2ll(p+usehash,plen-usehash,&loffset) == 0) {
  210. addReplyError(c,err);
  211. return C_ERR;
  212. }
  213. /* Adjust the offset by 'bits' for #<offset> form. */
  214. if (usehash) loffset *= bits;
  215. /* Limit offset to server.proto_max_bulk_len (512MB in bytes by default) */
  216. if ((loffset < 0) || (loffset >> 3) >= server.proto_max_bulk_len)
  217. {
  218. addReplyError(c,err);
  219. return C_ERR;
  220. }
  221. *offset = loffset;
  222. return C_OK;
  223. }
  224. /* This helper function for BITFIELD parses a bitfield type in the form
  225. * <sign><bits> where sign is 'u' or 'i' for unsigned and signed, and
  226. * the bits is a value between 1 and 64. However 64 bits unsigned integers
  227. * are reported as an error because of current limitations of Redis protocol
  228. * to return unsigned integer values greater than INT64_MAX.
  229. *
  230. * On error C_ERR is returned and an error is sent to the client. */
  231. int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) {
  232. char *p = o->ptr;
  233. char *err = "Invalid bitfield type. Use something like i16 u8. Note that u64 is not supported but i64 is.";
  234. long long llbits;
  235. if (p[0] == 'i') {
  236. *sign = 1;
  237. } else if (p[0] == 'u') {
  238. *sign = 0;
  239. } else {
  240. addReplyError(c,err);
  241. return C_ERR;
  242. }
  243. if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 ||
  244. llbits < 1 ||
  245. (*sign == 1 && llbits > 64) ||
  246. (*sign == 0 && llbits > 63))
  247. {
  248. addReplyError(c,err);
  249. return C_ERR;
  250. }
  251. *bits = llbits;
  252. return C_OK;
  253. }

相关技术文章

点击QQ咨询
开通会员
返回顶部
×
微信扫码支付
微信扫码支付
确定支付下载
请使用微信描二维码支付
×

提示信息

×

选择支付方式

  • 微信支付
  • 支付宝付款
确定支付下载