REORG: include: move integer manipulation functions from standard.h to intops.h
There are quite a number of integer manipulation functions defined in
standard.h, which is one of the reasons why standard.h is included from
many places and participates to the dependencies loop.
Let's just have a new file, intops.h to place all these operations.
These are a few bitops, 32/64 bit mul/div/rotate, integer parsing and
encoding (including varints), the full avalanche hash function, and
the my_htonll/my_ntohll functions.
For now no new C file was created for these yet.
diff --git a/include/common/standard.h b/include/common/standard.h
index 2f1dffe..7a2ba2e 100644
--- a/include/common/standard.h
+++ b/include/common/standard.h
@@ -38,6 +38,7 @@
#include <netinet/in.h>
#include <arpa/inet.h>
#include <haproxy/api.h>
+#include <haproxy/intops.h>
#include <common/chunk.h>
#include <common/namespace.h>
#include <import/eb32tree.h>
@@ -75,26 +76,6 @@
/* return the largest possible integer of type <ret>, with all bits set */
#define MAX_RANGE(ret) (~(typeof(ret))0)
-/* rotate left a 64-bit integer by <bits:[0-5]> bits */
-static inline uint64_t rotl64(uint64_t v, uint8_t bits)
-{
-#if !defined(__ARM_ARCH_8A) && !defined(__x86_64__)
- bits &= 63;
-#endif
- v = (v << bits) | (v >> (-bits & 63));
- return v;
-}
-
-/* rotate right a 64-bit integer by <bits:[0-5]> bits */
-static inline uint64_t rotr64(uint64_t v, uint8_t bits)
-{
-#if !defined(__ARM_ARCH_8A) && !defined(__x86_64__)
- bits &= 63;
-#endif
- v = (v >> bits) | (v << (-bits & 63));
- return v;
-}
-
/* DEFNULL() returns either the argument as-is, or NULL if absent. This is for
* use in macros arguments.
*/
@@ -241,104 +222,6 @@
return ret;
}
-/* returns the number of bytes needed to encode <v> as a varint. Be careful, use
- * it only with constants as it generates a large code (typ. 180 bytes). Use the
- * varint_bytes() version instead in case of doubt.
- */
-int varint_bytes(uint64_t v);
-static inline int __varint_bytes(uint64_t v)
-{
- switch (v) {
- case 0x0000000000000000 ... 0x00000000000000ef: return 1;
- case 0x00000000000000f0 ... 0x00000000000008ef: return 2;
- case 0x00000000000008f0 ... 0x00000000000408ef: return 3;
- case 0x00000000000408f0 ... 0x00000000020408ef: return 4;
- case 0x00000000020408f0 ... 0x00000001020408ef: return 5;
- case 0x00000001020408f0 ... 0x00000081020408ef: return 6;
- case 0x00000081020408f0 ... 0x00004081020408ef: return 7;
- case 0x00004081020408f0 ... 0x00204081020408ef: return 8;
- case 0x00204081020408f0 ... 0x10204081020408ef: return 9;
- default: return 10;
- }
-}
-
-/* Encode the integer <i> into a varint (variable-length integer). The encoded
- * value is copied in <*buf>. Here is the encoding format:
- *
- * 0 <= X < 240 : 1 byte (7.875 bits) [ XXXX XXXX ]
- * 240 <= X < 2288 : 2 bytes (11 bits) [ 1111 XXXX ] [ 0XXX XXXX ]
- * 2288 <= X < 264432 : 3 bytes (18 bits) [ 1111 XXXX ] [ 1XXX XXXX ] [ 0XXX XXXX ]
- * 264432 <= X < 33818864 : 4 bytes (25 bits) [ 1111 XXXX ] [ 1XXX XXXX ]*2 [ 0XXX XXXX ]
- * 33818864 <= X < 4328786160 : 5 bytes (32 bits) [ 1111 XXXX ] [ 1XXX XXXX ]*3 [ 0XXX XXXX ]
- * ...
- *
- * On success, it returns the number of written bytes and <*buf> is moved after
- * the encoded value. Otherwise, it returns -1. */
-static inline int
-encode_varint(uint64_t i, char **buf, char *end)
-{
- unsigned char *p = (unsigned char *)*buf;
- int r;
-
- if (p >= (unsigned char *)end)
- return -1;
-
- if (i < 240) {
- *p++ = i;
- *buf = (char *)p;
- return 1;
- }
-
- *p++ = (unsigned char)i | 240;
- i = (i - 240) >> 4;
- while (i >= 128) {
- if (p >= (unsigned char *)end)
- return -1;
- *p++ = (unsigned char)i | 128;
- i = (i - 128) >> 7;
- }
-
- if (p >= (unsigned char *)end)
- return -1;
- *p++ = (unsigned char)i;
-
- r = ((char *)p - *buf);
- *buf = (char *)p;
- return r;
-}
-
-/* Decode a varint from <*buf> and save the decoded value in <*i>. See
- * 'spoe_encode_varint' for details about varint.
- * On success, it returns the number of read bytes and <*buf> is moved after the
- * varint. Otherwise, it returns -1. */
-static inline int
-decode_varint(char **buf, char *end, uint64_t *i)
-{
- unsigned char *p = (unsigned char *)*buf;
- int r;
-
- if (p >= (unsigned char *)end)
- return -1;
-
- *i = *p++;
- if (*i < 240) {
- *buf = (char *)p;
- return 1;
- }
-
- r = 4;
- do {
- if (p >= (unsigned char *)end)
- return -1;
- *i += (uint64_t)*p << r;
- r += 7;
- } while (*p++ >= 128);
-
- r = ((char *)p - *buf);
- *buf = (char *)p;
- return r;
-}
-
/* returns a locally allocated string containing the quoted encoding of the
* input string. The output may be truncated to QSTR_SIZE chars, but it is
* guaranteed that the string will always be properly terminated. Quotes are
@@ -368,24 +251,6 @@
extern int ishex(char s);
/*
- * Return integer equivalent of character <c> for a hex digit (0-9, a-f, A-F),
- * otherwise -1. This compact form helps gcc produce efficient code.
- */
-static inline int hex2i(int c)
-{
- if ((unsigned char)(c -= '0') > 9) {
- if ((unsigned char)(c -= 'A' - '0') > 5 &&
- (unsigned char)(c -= 'a' - 'A') > 5)
- c = -11;
- c += 10;
- }
- return c;
-}
-
-/* rounds <i> down to the closest value having max 2 digits */
-unsigned int round_2dig(unsigned int i);
-
-/*
* Checks <name> for invalid characters. Valid chars are [A-Za-z0-9_:.-]. If an
* invalid character is found, a pointer to it is returned. If everything is
* fine, NULL is returned.
@@ -625,101 +490,6 @@
*/
int url_decode(char *string, int in_form);
-/* This one is 6 times faster than strtoul() on athlon, but does
- * no check at all.
- */
-static inline unsigned int __str2ui(const char *s)
-{
- unsigned int i = 0;
- while (*s) {
- i = i * 10 - '0';
- i += (unsigned char)*s++;
- }
- return i;
-}
-
-/* This one is 5 times faster than strtoul() on athlon with checks.
- * It returns the value of the number composed of all valid digits read.
- */
-static inline unsigned int __str2uic(const char *s)
-{
- unsigned int i = 0;
- unsigned int j;
- while (1) {
- j = (*s++) - '0';
- if (j > 9)
- break;
- i *= 10;
- i += j;
- }
- return i;
-}
-
-/* This one is 28 times faster than strtoul() on athlon, but does
- * no check at all!
- */
-static inline unsigned int __strl2ui(const char *s, int len)
-{
- unsigned int i = 0;
- while (len-- > 0) {
- i = i * 10 - '0';
- i += (unsigned char)*s++;
- }
- return i;
-}
-
-/* This one is 7 times faster than strtoul() on athlon with checks.
- * It returns the value of the number composed of all valid digits read.
- */
-static inline unsigned int __strl2uic(const char *s, int len)
-{
- unsigned int i = 0;
- unsigned int j, k;
-
- while (len-- > 0) {
- j = (*s++) - '0';
- k = i * 10;
- if (j > 9)
- break;
- i = k + j;
- }
- return i;
-}
-
-/* This function reads an unsigned integer from the string pointed to by <s>
- * and returns it. The <s> pointer is adjusted to point to the first unread
- * char. The function automatically stops at <end>.
- */
-static inline unsigned int __read_uint(const char **s, const char *end)
-{
- const char *ptr = *s;
- unsigned int i = 0;
- unsigned int j, k;
-
- while (ptr < end) {
- j = *ptr - '0';
- k = i * 10;
- if (j > 9)
- break;
- i = k + j;
- ptr++;
- }
- *s = ptr;
- return i;
-}
-
-unsigned long long int read_uint64(const char **s, const char *end);
-long long int read_int64(const char **s, const char *end);
-
-extern unsigned int str2ui(const char *s);
-extern unsigned int str2uic(const char *s);
-extern unsigned int strl2ui(const char *s, int len);
-extern unsigned int strl2uic(const char *s, int len);
-extern int strl2ic(const char *s, int len);
-extern int strl2irc(const char *s, int len, int *ret);
-extern int strl2llrc(const char *s, int len, long long *ret);
-extern int strl2llrc_dotted(const char *text, int len, long long *ret);
-extern unsigned int read_uint(const char **s, const char *end);
unsigned int inetaddr_host(const char *text);
unsigned int inetaddr_host_lim(const char *text, const char *stop);
unsigned int inetaddr_host_lim_ret(char *text, char *stop, char **ret);
@@ -836,168 +606,6 @@
#define HOUR (60 * MINUTE)
#define DAY (24 * HOUR)
-/* Multiply the two 32-bit operands and shift the 64-bit result right 32 bits.
- * This is used to compute fixed ratios by setting one of the operands to
- * (2^32*ratio).
- */
-static inline unsigned int mul32hi(unsigned int a, unsigned int b)
-{
- return ((unsigned long long)a * b) >> 32;
-}
-
-/* gcc does not know when it can safely divide 64 bits by 32 bits. Use this
- * function when you know for sure that the result fits in 32 bits, because
- * it is optimal on x86 and on 64bit processors.
- */
-static inline unsigned int div64_32(unsigned long long o1, unsigned int o2)
-{
- unsigned long long result;
-#ifdef __i386__
- asm("divl %2"
- : "=A" (result)
- : "A"(o1), "rm"(o2));
-#else
- result = o1 / o2;
-#endif
- return result;
-}
-
-/* Simple popcountl implementation. It returns the number of ones in a word.
- * Described here : https://graphics.stanford.edu/~seander/bithacks.html
- */
-static inline unsigned int my_popcountl(unsigned long a)
-{
- a = a - ((a >> 1) & ~0UL/3);
- a = (a & ~0UL/15*3) + ((a >> 2) & ~0UL/15*3);
- a = (a + (a >> 4)) & ~0UL/255*15;
- return (unsigned long)(a * (~0UL/255)) >> (sizeof(unsigned long) - 1) * 8;
-}
-
-/* returns non-zero if <a> has at least 2 bits set */
-static inline unsigned long atleast2(unsigned long a)
-{
- return a & (a - 1);
-}
-
-/* Simple ffs implementation. It returns the position of the lowest bit set to
- * one, starting at 1. It is illegal to call it with a==0 (undefined result).
- */
-static inline unsigned int my_ffsl(unsigned long a)
-{
- unsigned long cnt;
-
-#if defined(__x86_64__)
- __asm__("bsf %1,%0\n" : "=r" (cnt) : "rm" (a));
- cnt++;
-#else
-
- cnt = 1;
-#if LONG_MAX > 0x7FFFFFFFL /* 64bits */
- if (!(a & 0xFFFFFFFFUL)) {
- a >>= 32;
- cnt += 32;
- }
-#endif
- if (!(a & 0XFFFFU)) {
- a >>= 16;
- cnt += 16;
- }
- if (!(a & 0XFF)) {
- a >>= 8;
- cnt += 8;
- }
- if (!(a & 0xf)) {
- a >>= 4;
- cnt += 4;
- }
- if (!(a & 0x3)) {
- a >>= 2;
- cnt += 2;
- }
- if (!(a & 0x1)) {
- cnt += 1;
- }
-#endif /* x86_64 */
-
- return cnt;
-}
-
-/* Simple fls implementation. It returns the position of the highest bit set to
- * one, starting at 1. It is illegal to call it with a==0 (undefined result).
- */
-static inline unsigned int my_flsl(unsigned long a)
-{
- unsigned long cnt;
-
-#if defined(__x86_64__)
- __asm__("bsr %1,%0\n" : "=r" (cnt) : "rm" (a));
- cnt++;
-#else
-
- cnt = 1;
-#if LONG_MAX > 0x7FFFFFFFUL /* 64bits */
- if (a & 0xFFFFFFFF00000000UL) {
- a >>= 32;
- cnt += 32;
- }
-#endif
- if (a & 0XFFFF0000U) {
- a >>= 16;
- cnt += 16;
- }
- if (a & 0XFF00) {
- a >>= 8;
- cnt += 8;
- }
- if (a & 0xf0) {
- a >>= 4;
- cnt += 4;
- }
- if (a & 0xc) {
- a >>= 2;
- cnt += 2;
- }
- if (a & 0x2) {
- cnt += 1;
- }
-#endif /* x86_64 */
-
- return cnt;
-}
-
-/* Build a word with the <bits> lower bits set (reverse of my_popcountl) */
-static inline unsigned long nbits(int bits)
-{
- if (--bits < 0)
- return 0;
- else
- return (2UL << bits) - 1;
-}
-
-/* sets bit <bit> into map <map>, which must be long-aligned */
-static inline void ha_bit_set(unsigned long bit, long *map)
-{
- map[bit / (8 * sizeof(*map))] |= 1UL << (bit & (8 * sizeof(*map) - 1));
-}
-
-/* clears bit <bit> from map <map>, which must be long-aligned */
-static inline void ha_bit_clr(unsigned long bit, long *map)
-{
- map[bit / (8 * sizeof(*map))] &= ~(1UL << (bit & (8 * sizeof(*map) - 1)));
-}
-
-/* flips bit <bit> from map <map>, which must be long-aligned */
-static inline void ha_bit_flip(unsigned long bit, long *map)
-{
- map[bit / (8 * sizeof(*map))] ^= 1UL << (bit & (8 * sizeof(*map) - 1));
-}
-
-/* returns non-zero if bit <bit> from map <map> is set, otherwise 0 */
-static inline int ha_bit_test(unsigned long bit, const long *map)
-{
- return !!(map[bit / (8 * sizeof(*map))] & 1UL << (bit & (8 * sizeof(*map) - 1)));
-}
-
/*
* Parse binary string written in hexadecimal (source) and store the decoded
* result into binstr and set binstrlen to the length of binstr. Memory for
@@ -1062,44 +670,6 @@
/* returns an operator among STD_OP_* for string <str> or < 0 if unknown */
int get_std_op(const char *str);
-/* hash a 32-bit integer to another 32-bit integer */
-extern unsigned int full_hash(unsigned int a);
-static inline unsigned int __full_hash(unsigned int a)
-{
- /* This function is one of Bob Jenkins' full avalanche hashing
- * functions, which when provides quite a good distribution for little
- * input variations. The result is quite suited to fit over a 32-bit
- * space with enough variations so that a randomly picked number falls
- * equally before any server position.
- * Check http://burtleburtle.net/bob/hash/integer.html for more info.
- */
- a = (a+0x7ed55d16) + (a<<12);
- a = (a^0xc761c23c) ^ (a>>19);
- a = (a+0x165667b1) + (a<<5);
- a = (a+0xd3a2646c) ^ (a<<9);
- a = (a+0xfd7046c5) + (a<<3);
- a = (a^0xb55a4f09) ^ (a>>16);
-
- /* ensure values are better spread all around the tree by multiplying
- * by a large prime close to 3/4 of the tree.
- */
- return a * 3221225473U;
-}
-
-/* Return the bit position in mask <m> of the nth bit set of rank <r>, between
- * 0 and LONGBITS-1 included, starting from the left. For example ranks 0,1,2,3
- * for mask 0x55 will be 6, 4, 2 and 0 respectively. This algorithm is based on
- * a popcount variant and is described here :
- * https://graphics.stanford.edu/~seander/bithacks.html
- */
-unsigned int mask_find_rank_bit(unsigned int r, unsigned long m);
-unsigned int mask_find_rank_bit_fast(unsigned int r, unsigned long m,
- unsigned long a, unsigned long b,
- unsigned long c, unsigned long d);
-void mask_prep_rank_map(unsigned long m,
- unsigned long *a, unsigned long *b,
- unsigned long *c, unsigned long *d);
-
/* sets the address family to AF_UNSPEC so that is_addr() does not match */
static inline void clear_addr(struct sockaddr_storage *addr)
{
@@ -1451,39 +1021,6 @@
return code & 0x0f;
}
-/* Turns 64-bit value <a> from host byte order to network byte order.
- * The principle consists in letting the compiler detect we're playing
- * with a union and simplify most or all operations. The asm-optimized
- * htonl() version involving bswap (x86) / rev (arm) / other is a single
- * operation on little endian, or a NOP on big-endian. In both cases,
- * this lets the compiler "see" that we're rebuilding a 64-bit word from
- * two 32-bit quantities that fit into a 32-bit register. In big endian,
- * the whole code is optimized out. In little endian, with a decent compiler,
- * a few bswap and 2 shifts are left, which is the minimum acceptable.
- */
-static inline unsigned long long my_htonll(unsigned long long a)
-{
-#if defined(__x86_64__)
- __asm__ volatile("bswap %0" : "=r"(a) : "0"(a));
- return a;
-#else
- union {
- struct {
- unsigned int w1;
- unsigned int w2;
- } by32;
- unsigned long long by64;
- } w = { .by64 = a };
- return ((unsigned long long)htonl(w.by32.w1) << 32) | htonl(w.by32.w2);
-#endif
-}
-
-/* Turns 64-bit value <a> from network byte order to host byte order. */
-static inline unsigned long long my_ntohll(unsigned long long a)
-{
- return my_htonll(a);
-}
-
/* returns a 64-bit a timestamp with the finest resolution available. The
* unit is intentionally not specified. It's mostly used to compare dates.
*/
diff --git a/include/haproxy/intops.h b/include/haproxy/intops.h
new file mode 100644
index 0000000..960c6cb
--- /dev/null
+++ b/include/haproxy/intops.h
@@ -0,0 +1,494 @@
+/*
+ * include/haproxy/intops.h
+ * Functions for integer operations.
+ *
+ * Copyright (C) 2020 Willy Tarreau - w@1wt.eu
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+*/
+
+#ifndef _HAPROXY_INTOPS_H
+#define _HAPROXY_INTOPS_H
+
+#include <haproxy/api.h>
+
+/* exported functions, mostly integer parsing */
+/* rounds <i> down to the closest value having max 2 digits */
+unsigned int round_2dig(unsigned int i);
+unsigned int full_hash(unsigned int a);
+int varint_bytes(uint64_t v);
+unsigned int read_uint(const char **s, const char *end);
+long long read_int64(const char **s, const char *end);
+unsigned long long read_uint64(const char **s, const char *end);
+unsigned int str2ui(const char *s);
+unsigned int str2uic(const char *s);
+unsigned int strl2ui(const char *s, int len);
+unsigned int strl2uic(const char *s, int len);
+int strl2ic(const char *s, int len);
+int strl2irc(const char *s, int len, int *ret);
+int strl2llrc(const char *s, int len, long long *ret);
+int strl2llrc_dotted(const char *text, int len, long long *ret);
+unsigned int mask_find_rank_bit(unsigned int r, unsigned long m);
+unsigned int mask_find_rank_bit_fast(unsigned int r, unsigned long m,
+ unsigned long a, unsigned long b,
+ unsigned long c, unsigned long d);
+void mask_prep_rank_map(unsigned long m,
+ unsigned long *a, unsigned long *b,
+ unsigned long *c, unsigned long *d);
+
+
+/* Multiply the two 32-bit operands and shift the 64-bit result right 32 bits.
+ * This is used to compute fixed ratios by setting one of the operands to
+ * (2^32*ratio).
+ */
+static inline unsigned int mul32hi(unsigned int a, unsigned int b)
+{
+ return ((unsigned long long)a * b) >> 32;
+}
+
+/* gcc does not know when it can safely divide 64 bits by 32 bits. Use this
+ * function when you know for sure that the result fits in 32 bits, because
+ * it is optimal on x86 and on 64bit processors.
+ */
+static inline unsigned int div64_32(unsigned long long o1, unsigned int o2)
+{
+ unsigned long long result;
+#ifdef __i386__
+ asm("divl %2"
+ : "=A" (result)
+ : "A"(o1), "rm"(o2));
+#else
+ result = o1 / o2;
+#endif
+ return result;
+}
+
+/* rotate left a 64-bit integer by <bits:[0-5]> bits */
+static inline uint64_t rotl64(uint64_t v, uint8_t bits)
+{
+#if !defined(__ARM_ARCH_8A) && !defined(__x86_64__)
+ bits &= 63;
+#endif
+ v = (v << bits) | (v >> (-bits & 63));
+ return v;
+}
+
+/* rotate right a 64-bit integer by <bits:[0-5]> bits */
+static inline uint64_t rotr64(uint64_t v, uint8_t bits)
+{
+#if !defined(__ARM_ARCH_8A) && !defined(__x86_64__)
+ bits &= 63;
+#endif
+ v = (v >> bits) | (v << (-bits & 63));
+ return v;
+}
+
+/* Simple popcountl implementation. It returns the number of ones in a word.
+ * Described here : https://graphics.stanford.edu/~seander/bithacks.html
+ */
+static inline unsigned int my_popcountl(unsigned long a)
+{
+ a = a - ((a >> 1) & ~0UL/3);
+ a = (a & ~0UL/15*3) + ((a >> 2) & ~0UL/15*3);
+ a = (a + (a >> 4)) & ~0UL/255*15;
+ return (unsigned long)(a * (~0UL/255)) >> (sizeof(unsigned long) - 1) * 8;
+}
+
+/* returns non-zero if <a> has at least 2 bits set */
+static inline unsigned long atleast2(unsigned long a)
+{
+ return a & (a - 1);
+}
+
+/* Simple ffs implementation. It returns the position of the lowest bit set to
+ * one, starting at 1. It is illegal to call it with a==0 (undefined result).
+ */
+static inline unsigned int my_ffsl(unsigned long a)
+{
+ unsigned long cnt;
+
+#if defined(__x86_64__)
+ __asm__("bsf %1,%0\n" : "=r" (cnt) : "rm" (a));
+ cnt++;
+#else
+
+ cnt = 1;
+#if LONG_MAX > 0x7FFFFFFFL /* 64bits */
+ if (!(a & 0xFFFFFFFFUL)) {
+ a >>= 32;
+ cnt += 32;
+ }
+#endif
+ if (!(a & 0XFFFFU)) {
+ a >>= 16;
+ cnt += 16;
+ }
+ if (!(a & 0XFF)) {
+ a >>= 8;
+ cnt += 8;
+ }
+ if (!(a & 0xf)) {
+ a >>= 4;
+ cnt += 4;
+ }
+ if (!(a & 0x3)) {
+ a >>= 2;
+ cnt += 2;
+ }
+ if (!(a & 0x1)) {
+ cnt += 1;
+ }
+#endif /* x86_64 */
+
+ return cnt;
+}
+
+/* Simple fls implementation. It returns the position of the highest bit set to
+ * one, starting at 1. It is illegal to call it with a==0 (undefined result).
+ */
+static inline unsigned int my_flsl(unsigned long a)
+{
+ unsigned long cnt;
+
+#if defined(__x86_64__)
+ __asm__("bsr %1,%0\n" : "=r" (cnt) : "rm" (a));
+ cnt++;
+#else
+
+ cnt = 1;
+#if LONG_MAX > 0x7FFFFFFFUL /* 64bits */
+ if (a & 0xFFFFFFFF00000000UL) {
+ a >>= 32;
+ cnt += 32;
+ }
+#endif
+ if (a & 0XFFFF0000U) {
+ a >>= 16;
+ cnt += 16;
+ }
+ if (a & 0XFF00) {
+ a >>= 8;
+ cnt += 8;
+ }
+ if (a & 0xf0) {
+ a >>= 4;
+ cnt += 4;
+ }
+ if (a & 0xc) {
+ a >>= 2;
+ cnt += 2;
+ }
+ if (a & 0x2) {
+ cnt += 1;
+ }
+#endif /* x86_64 */
+
+ return cnt;
+}
+
+/* Build a word with the <bits> lower bits set (reverse of my_popcountl) */
+static inline unsigned long nbits(int bits)
+{
+ if (--bits < 0)
+ return 0;
+ else
+ return (2UL << bits) - 1;
+}
+
+/* Turns 64-bit value <a> from host byte order to network byte order.
+ * The principle consists in letting the compiler detect we're playing
+ * with a union and simplify most or all operations. The asm-optimized
+ * htonl() version involving bswap (x86) / rev (arm) / other is a single
+ * operation on little endian, or a NOP on big-endian. In both cases,
+ * this lets the compiler "see" that we're rebuilding a 64-bit word from
+ * two 32-bit quantities that fit into a 32-bit register. In big endian,
+ * the whole code is optimized out. In little endian, with a decent compiler,
+ * a few bswap and 2 shifts are left, which is the minimum acceptable.
+ */
+static inline unsigned long long my_htonll(unsigned long long a)
+{
+#if defined(__x86_64__)
+ __asm__ volatile("bswap %0" : "=r"(a) : "0"(a));
+ return a;
+#else
+ union {
+ struct {
+ unsigned int w1;
+ unsigned int w2;
+ } by32;
+ unsigned long long by64;
+ } w = { .by64 = a };
+ return ((unsigned long long)htonl(w.by32.w1) << 32) | htonl(w.by32.w2);
+#endif
+}
+
+/* Turns 64-bit value <a> from network byte order to host byte order. */
+static inline unsigned long long my_ntohll(unsigned long long a)
+{
+ return my_htonll(a);
+}
+
+/* sets bit <bit> into map <map>, which must be long-aligned */
+static inline void ha_bit_set(unsigned long bit, long *map)
+{
+ map[bit / (8 * sizeof(*map))] |= 1UL << (bit & (8 * sizeof(*map) - 1));
+}
+
+/* clears bit <bit> from map <map>, which must be long-aligned */
+static inline void ha_bit_clr(unsigned long bit, long *map)
+{
+ map[bit / (8 * sizeof(*map))] &= ~(1UL << (bit & (8 * sizeof(*map) - 1)));
+}
+
+/* flips bit <bit> from map <map>, which must be long-aligned */
+static inline void ha_bit_flip(unsigned long bit, long *map)
+{
+ map[bit / (8 * sizeof(*map))] ^= 1UL << (bit & (8 * sizeof(*map) - 1));
+}
+
+/* returns non-zero if bit <bit> from map <map> is set, otherwise 0 */
+static inline int ha_bit_test(unsigned long bit, const long *map)
+{
+ return !!(map[bit / (8 * sizeof(*map))] & 1UL << (bit & (8 * sizeof(*map) - 1)));
+}
+
+/* hash a 32-bit integer to another 32-bit integer. This code may be large when
+ * inlined, use full_hash() instead.
+ */
+static inline unsigned int __full_hash(unsigned int a)
+{
+ /* This function is one of Bob Jenkins' full avalanche hashing
+ * functions, which when provides quite a good distribution for little
+ * input variations. The result is quite suited to fit over a 32-bit
+ * space with enough variations so that a randomly picked number falls
+ * equally before any server position.
+ * Check http://burtleburtle.net/bob/hash/integer.html for more info.
+ */
+ a = (a+0x7ed55d16) + (a<<12);
+ a = (a^0xc761c23c) ^ (a>>19);
+ a = (a+0x165667b1) + (a<<5);
+ a = (a+0xd3a2646c) ^ (a<<9);
+ a = (a+0xfd7046c5) + (a<<3);
+ a = (a^0xb55a4f09) ^ (a>>16);
+
+ /* ensure values are better spread all around the tree by multiplying
+ * by a large prime close to 3/4 of the tree.
+ */
+ return a * 3221225473U;
+}
+
+/*
+ * Return integer equivalent of character <c> for a hex digit (0-9, a-f, A-F),
+ * otherwise -1. This compact form helps gcc produce efficient code.
+ */
+static inline int hex2i(int c)
+{
+ if ((unsigned char)(c -= '0') > 9) {
+ if ((unsigned char)(c -= 'A' - '0') > 5 &&
+ (unsigned char)(c -= 'a' - 'A') > 5)
+ c = -11;
+ c += 10;
+ }
+ return c;
+}
+
+/* This one is 6 times faster than strtoul() on athlon, but does
+ * no check at all.
+ */
+static inline unsigned int __str2ui(const char *s)
+{
+ unsigned int i = 0;
+ while (*s) {
+ i = i * 10 - '0';
+ i += (unsigned char)*s++;
+ }
+ return i;
+}
+
+/* This one is 5 times faster than strtoul() on athlon with checks.
+ * It returns the value of the number composed of all valid digits read.
+ */
+static inline unsigned int __str2uic(const char *s)
+{
+ unsigned int i = 0;
+ unsigned int j;
+
+ while (1) {
+ j = (*s++) - '0';
+ if (j > 9)
+ break;
+ i *= 10;
+ i += j;
+ }
+ return i;
+}
+
+/* This one is 28 times faster than strtoul() on athlon, but does
+ * no check at all!
+ */
+static inline unsigned int __strl2ui(const char *s, int len)
+{
+ unsigned int i = 0;
+
+ while (len-- > 0) {
+ i = i * 10 - '0';
+ i += (unsigned char)*s++;
+ }
+ return i;
+}
+
+/* This one is 7 times faster than strtoul() on athlon with checks.
+ * It returns the value of the number composed of all valid digits read.
+ */
+static inline unsigned int __strl2uic(const char *s, int len)
+{
+ unsigned int i = 0;
+ unsigned int j, k;
+
+ while (len-- > 0) {
+ j = (*s++) - '0';
+ k = i * 10;
+ if (j > 9)
+ break;
+ i = k + j;
+ }
+ return i;
+}
+
+/* This function reads an unsigned integer from the string pointed to by <s>
+ * and returns it. The <s> pointer is adjusted to point to the first unread
+ * char. The function automatically stops at <end>.
+ */
+static inline unsigned int __read_uint(const char **s, const char *end)
+{
+ const char *ptr = *s;
+ unsigned int i = 0;
+ unsigned int j, k;
+
+ while (ptr < end) {
+ j = *ptr - '0';
+ k = i * 10;
+ if (j > 9)
+ break;
+ i = k + j;
+ ptr++;
+ }
+ *s = ptr;
+ return i;
+}
+
+/* returns the number of bytes needed to encode <v> as a varint. Be careful, use
+ * it only with constants as it generates a large code (typ. 180 bytes). Use the
+ * varint_bytes() version instead in case of doubt.
+ */
+static inline int __varint_bytes(uint64_t v)
+{
+ switch (v) {
+ case 0x0000000000000000 ... 0x00000000000000ef: return 1;
+ case 0x00000000000000f0 ... 0x00000000000008ef: return 2;
+ case 0x00000000000008f0 ... 0x00000000000408ef: return 3;
+ case 0x00000000000408f0 ... 0x00000000020408ef: return 4;
+ case 0x00000000020408f0 ... 0x00000001020408ef: return 5;
+ case 0x00000001020408f0 ... 0x00000081020408ef: return 6;
+ case 0x00000081020408f0 ... 0x00004081020408ef: return 7;
+ case 0x00004081020408f0 ... 0x00204081020408ef: return 8;
+ case 0x00204081020408f0 ... 0x10204081020408ef: return 9;
+ default: return 10;
+ }
+}
+
+/* Encode the integer <i> into a varint (variable-length integer). The encoded
+ * value is copied in <*buf>. Here is the encoding format:
+ *
+ * 0 <= X < 240 : 1 byte (7.875 bits) [ XXXX XXXX ]
+ * 240 <= X < 2288 : 2 bytes (11 bits) [ 1111 XXXX ] [ 0XXX XXXX ]
+ * 2288 <= X < 264432 : 3 bytes (18 bits) [ 1111 XXXX ] [ 1XXX XXXX ] [ 0XXX XXXX ]
+ * 264432 <= X < 33818864 : 4 bytes (25 bits) [ 1111 XXXX ] [ 1XXX XXXX ]*2 [ 0XXX XXXX ]
+ * 33818864 <= X < 4328786160 : 5 bytes (32 bits) [ 1111 XXXX ] [ 1XXX XXXX ]*3 [ 0XXX XXXX ]
+ * ...
+ *
+ * On success, it returns the number of written bytes and <*buf> is moved after
+ * the encoded value. Otherwise, it returns -1. */
+static inline int encode_varint(uint64_t i, char **buf, char *end)
+{
+ unsigned char *p = (unsigned char *)*buf;
+ int r;
+
+ if (p >= (unsigned char *)end)
+ return -1;
+
+ if (i < 240) {
+ *p++ = i;
+ *buf = (char *)p;
+ return 1;
+ }
+
+ *p++ = (unsigned char)i | 240;
+ i = (i - 240) >> 4;
+ while (i >= 128) {
+ if (p >= (unsigned char *)end)
+ return -1;
+ *p++ = (unsigned char)i | 128;
+ i = (i - 128) >> 7;
+ }
+
+ if (p >= (unsigned char *)end)
+ return -1;
+ *p++ = (unsigned char)i;
+
+ r = ((char *)p - *buf);
+ *buf = (char *)p;
+ return r;
+}
+
+/* Decode a varint from <*buf> and save the decoded value in <*i>. See
+ * 'spoe_encode_varint' for details about varint.
+ * On success, it returns the number of read bytes and <*buf> is moved after the
+ * varint. Otherwise, it returns -1. */
+static inline int decode_varint(char **buf, char *end, uint64_t *i)
+{
+ unsigned char *p = (unsigned char *)*buf;
+ int r;
+
+ if (p >= (unsigned char *)end)
+ return -1;
+
+ *i = *p++;
+ if (*i < 240) {
+ *buf = (char *)p;
+ return 1;
+ }
+
+ r = 4;
+ do {
+ if (p >= (unsigned char *)end)
+ return -1;
+ *i += (uint64_t)*p << r;
+ r += 7;
+ } while (*p++ >= 128);
+
+ r = ((char *)p - *buf);
+ *buf = (char *)p;
+ return r;
+}
+
+#endif /* _HAPROXY_INTOPS_H */
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */