Adding upstream version 3.8.1.upstream/3.8.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 632 insertions, 0 deletions

diff --git a/contrib/fpconv/CMakeLists.txt b/contrib/fpconv/CMakeLists.txt
new file mode 100644
index 0000000..b330525
--- /dev/null
+++ b/contrib/fpconv/CMakeLists.txt
@@ -0,0 +1,7 @@
+SET(FPCONVSRC            fpconv.c)
+
+SET(FTPCONV_COMPILE_FLAGS "-DRSPAMD_LIB")
+
+ADD_LIBRARY(rspamd-fpconv STATIC ${FPCONVSRC})
+SET_TARGET_PROPERTIES(rspamd-fpconv PROPERTIES VERSION ${RSPAMD_VERSION})
+SET_TARGET_PROPERTIES(rspamd-fpconv PROPERTIES COMPILE_FLAGS "${FTPCONV_COMPILE_FLAGS}")
\ No newline at end of file
diff --git a/contrib/fpconv/LICENSE b/contrib/fpconv/LICENSE
new file mode 100644
index 0000000..36b7cd9
--- /dev/null
+++ b/contrib/fpconv/LICENSE
@@ -0,0 +1,23 @@
+Boost Software License - Version 1.0 - August 17th, 2003
+
+Permission is hereby granted, free of charge, to any person or organization
+obtaining a copy of the software and accompanying documentation covered by
+this license (the "Software") to use, reproduce, display, distribute,
+execute, and transmit the Software, and to prepare derivative works of the
+Software, and to permit third-parties to whom the Software is furnished to
+do so, all subject to the following:
+
+The copyright notices in the Software and this entire statement, including
+the above license grant, this restriction and the following disclaimer,
+must be included in all copies of the Software, in whole or in part, and
+all derivative works of the Software, unless such copies or derivative
+works are solely in the form of machine-executable object code generated by
+a source language processor.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
+SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
+FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
diff --git a/contrib/fpconv/fpconv.c b/contrib/fpconv/fpconv.c
new file mode 100644
index 0000000..f8b601a
--- /dev/null
+++ b/contrib/fpconv/fpconv.c
@@ -0,0 +1,480 @@
+#include <stdbool.h>
+#include <string.h>
+#include <sys/param.h>
+
+#include "fpconv.h"
+#include "powers.h"
+
+#define fracmask  0x000FFFFFFFFFFFFFU
+#define expmask   0x7FF0000000000000U
+#define hiddenbit 0x0010000000000000U
+#define signmask  0x8000000000000000U
+#define expbias   (1023 + 52)
+
+#define absv(n) ((n) < 0 ? -(n) : (n))
+#define minv(a, b) ((a) < (b) ? (a) : (b))
+
+static uint64_t tens[] = {
+		10000000000000000000U, 1000000000000000000U, 100000000000000000U,
+		10000000000000000U, 1000000000000000U, 100000000000000U,
+		10000000000000U, 1000000000000U, 100000000000U,
+		10000000000U, 1000000000U, 100000000U,
+		10000000U, 1000000U, 100000U,
+		10000U, 1000U, 100U,
+		10U, 1U
+};
+
+static inline uint64_t get_dbits (double d) {
+	union {
+		double dbl;
+		uint64_t i;
+	} dbl_bits = {d};
+
+	return dbl_bits.i;
+}
+
+static Fp build_fp (double d) {
+	uint64_t bits = get_dbits (d);
+
+	Fp fp;
+	fp.frac = bits & fracmask;
+	fp.exp = (bits & expmask) >> 52u;
+
+	if (fp.exp) {
+		fp.frac += hiddenbit;
+		fp.exp -= expbias;
+
+	}
+	else {
+		fp.exp = -expbias + 1;
+	}
+
+	return fp;
+}
+
+static void normalize (Fp *fp) {
+	while ((fp->frac & hiddenbit) == 0) {
+		fp->frac <<= 1u;
+		fp->exp--;
+	}
+
+	const unsigned int shift = 64 - 52 - 1;
+	fp->frac <<= shift;
+	fp->exp -= shift;
+}
+
+static void get_normalized_boundaries (Fp *fp, Fp *lower, Fp *upper) {
+	upper->frac = (fp->frac << 1u) + 1u;
+	upper->exp = fp->exp - 1u;
+
+	while ((upper->frac & (hiddenbit << 1u)) == 0) {
+		upper->frac <<= 1u;
+		upper->exp--;
+	}
+
+	const unsigned int u_shift = 64 - 52 - 2;
+
+	upper->frac <<= u_shift;
+	upper->exp = upper->exp - u_shift;
+
+
+	unsigned int l_shift = fp->frac == hiddenbit ? 2u : 1u;
+
+	lower->frac = (fp->frac << l_shift) - 1;
+	lower->exp = fp->exp - l_shift;
+
+
+	lower->frac <<= lower->exp - upper->exp;
+	lower->exp = upper->exp;
+}
+
+static Fp multiply (Fp *a, Fp *b) {
+	const uint64_t lomask = 0x00000000FFFFFFFFu;
+
+	uint64_t ah_bl = (a->frac >> 32u) * (b->frac & lomask);
+	uint64_t al_bh = (a->frac & lomask) * (b->frac >> 32u);
+	uint64_t al_bl = (a->frac & lomask) * (b->frac & lomask);
+	uint64_t ah_bh = (a->frac >> 32u) * (b->frac >> 32u);
+
+	uint64_t tmp = (ah_bl & lomask) + (al_bh & lomask) + (al_bl >> 32u);
+	/* round up */
+	tmp += 1U << 31u;
+
+	Fp fp = {
+			ah_bh + (ah_bl >> 32u) + (al_bh >> 32u) + (tmp >> 32u),
+			a->exp + b->exp + 64u
+	};
+
+	return fp;
+}
+
+static void round_digit (char *digits, int ndigits, uint64_t delta, uint64_t rem, uint64_t kappa, uint64_t frac) {
+	while (rem < frac && delta - rem >= kappa &&
+		   (rem + kappa < frac || frac - rem > rem + kappa - frac)) {
+
+		digits[ndigits - 1]--;
+		rem += kappa;
+	}
+}
+
+static int generate_digits (Fp *fp, Fp *upper, Fp *lower, char *digits, int *K) {
+	uint64_t wfrac = upper->frac - fp->frac;
+	uint64_t delta = upper->frac - lower->frac;
+
+	Fp one;
+	one.frac = 1ULL << -upper->exp;
+	one.exp = upper->exp;
+
+	uint64_t part1 = upper->frac >> -one.exp;
+	uint64_t part2 = upper->frac & (one.frac - 1);
+
+	int idx = 0, kappa = 10;
+	uint64_t *divp;
+	/* 1000000000 */
+	for (divp = tens + 10; kappa > 0; divp++) {
+
+		uint64_t div = *divp;
+		unsigned digit = part1 / div;
+
+		if (digit || idx) {
+			digits[idx++] = digit + '0';
+		}
+
+		part1 -= digit * div;
+		kappa--;
+
+		uint64_t tmp = (part1 << -one.exp) + part2;
+		if (tmp <= delta) {
+			*K += kappa;
+			round_digit (digits, idx, delta, tmp, div << -one.exp, wfrac);
+
+			return idx;
+		}
+	}
+
+	/* 10 */
+	uint64_t *unit = tens + 18;
+
+	while (true) {
+		part2 *= 10;
+		delta *= 10;
+		kappa--;
+
+		unsigned digit = part2 >> -one.exp;
+		if (digit || idx) {
+			digits[idx++] = digit + '0';
+		}
+
+		part2 &= one.frac - 1;
+		if (part2 < delta) {
+			*K += kappa;
+			round_digit (digits, idx, delta, part2, one.frac, wfrac * *unit);
+
+			return idx;
+		}
+
+		unit--;
+	}
+}
+
+static int grisu2 (double d, char *digits, int *K) {
+	Fp w = build_fp (d);
+
+	Fp lower, upper;
+	get_normalized_boundaries (&w, &lower, &upper);
+
+	normalize (&w);
+
+	int k;
+	Fp cp = find_cachedpow10 (upper.exp, &k);
+
+	w = multiply (&w, &cp);
+	upper = multiply (&upper, &cp);
+	lower = multiply (&lower, &cp);
+
+	lower.frac++;
+	upper.frac--;
+
+	*K = -k;
+
+	return generate_digits (&w, &upper, &lower, digits, K);
+}
+
+static inline int emit_integer (char *digits, int ndigits,
+								char *dest, int K, bool neg,
+								unsigned precision)
+{
+	char *d = dest;
+
+	memcpy (d, digits, ndigits);
+	d += ndigits;
+	memset (d, '0', K);
+	d += K;
+
+	precision = MIN(precision, FPCONV_BUFLEN - (ndigits + K + 1));
+
+	if (precision) {
+		*d++ = '.';
+		memset (d, '0', precision);
+		d += precision;
+	}
+
+	return d - dest;
+}
+
+static inline int emit_scientific_digits (char *digits, int ndigits,
+									 char *dest, int K, bool neg,
+									 unsigned precision, int exp)
+{
+	/* write decimal w/ scientific notation */
+	ndigits = minv(ndigits, 18 - neg);
+
+	int idx = 0;
+	dest[idx++] = digits[0];
+
+	if (ndigits > 1) {
+		dest[idx++] = '.';
+		memcpy(dest + idx, digits + 1, ndigits - 1);
+		idx += ndigits - 1;
+	}
+
+	dest[idx++] = 'e';
+
+	char sign = K + ndigits - 1 < 0 ? '-' : '+';
+	dest[idx++] = sign;
+
+	int cent = 0;
+
+	if (exp > 99) {
+		cent = exp / 100;
+		dest[idx++] = cent + '0';
+		exp -= cent * 100;
+	}
+	if (exp > 9) {
+		int dec = exp / 10;
+		dest[idx++] = dec + '0';
+		exp -= dec * 10;
+
+	}
+	else if (cent) {
+		dest[idx++] = '0';
+	}
+
+	dest[idx++] = exp % 10 + '0';
+
+	return idx;
+}
+
+static inline int emit_fixed_digits (char *digits, int ndigits,
+									 char *dest, int K, bool neg,
+									 unsigned precision, int exp)
+{
+	int offset = ndigits - absv(K), to_print;
+	/* fp < 1.0 -> write leading zero */
+	if (K < 0) {
+		if (offset <= 0) {
+			if (precision) {
+				if (-offset >= precision) {
+					/* Just print 0.[0]{precision} */
+					dest[0] = '0';
+					dest[1] = '.';
+					memset(dest + 2, '0', precision);
+
+					return precision + 2;
+				}
+
+				to_print = MAX(ndigits - offset, precision);
+			}
+			else {
+				to_print = ndigits - offset;
+			}
+
+			if (to_print <= FPCONV_BUFLEN - 3) {
+				offset = -offset;
+				dest[0] = '0';
+				dest[1] = '.';
+				memset(dest + 2, '0', offset);
+
+				if (precision) {
+					/* The case where offset > precision is covered previously */
+					precision -= offset;
+
+					if (precision <= ndigits) {
+						/* Truncate or leave as is */
+						memcpy(dest + offset + 2, digits, precision);
+
+						return precision + 2 + offset;
+					}
+					else {
+						/* Expand */
+						memcpy(dest + offset + 2, digits, ndigits);
+						precision -= ndigits;
+						memset(dest + offset + 2 + ndigits, '0', precision);
+
+						return ndigits + 2 + offset + precision;
+					}
+				}
+				else {
+					memcpy(dest + offset + 2, digits, ndigits);
+				}
+
+				return ndigits + 2 + offset;
+			}
+			else {
+				return emit_scientific_digits (digits, ndigits, dest, K, neg, precision, exp);
+			}
+		}
+		else {
+			/*
+			 * fp > 1.0, if offset > 0 then we have less digits than
+			 * fp exponent, so we need to switch to scientific notation to
+			 * display number at least more or less precisely
+			 */
+			if (offset > 0 && ndigits <= FPCONV_BUFLEN - 3) {
+				char *d = dest;
+				memcpy(d, digits, offset);
+				d += offset;
+				*d++ = '.';
+
+				ndigits -= offset;
+
+				if (precision) {
+					if (ndigits >= precision) {
+						/* Truncate or leave as is */
+						memcpy(d, digits + offset, precision);
+						d += precision;
+					}
+					else {
+						/* Expand */
+						memcpy(d, digits + offset, ndigits);
+						precision -= ndigits;
+						d += ndigits;
+
+						/* Check if we have enough bufspace */
+						if ((d - dest) + precision <= FPCONV_BUFLEN) {
+							memset (d, '0', precision);
+							d += precision;
+						}
+						else {
+							memset (d, '0', FPCONV_BUFLEN - (d - dest));
+							d += FPCONV_BUFLEN - (d - dest);
+						}
+					}
+				}
+				else {
+					memcpy(d, digits + offset, ndigits);
+					d += ndigits;
+				}
+
+				return d - dest;
+			}
+		}
+	}
+
+	return emit_scientific_digits (digits, ndigits, dest, K, neg, precision, exp);
+}
+
+static int emit_digits (char *digits, int ndigits, char *dest, int K, bool neg,
+						unsigned precision, bool scientific)
+{
+	int exp = absv(K + ndigits - 1);
+
+	/* write plain integer */
+	if (K >= 0 && (exp < (ndigits + 7))) {
+		return emit_integer (digits, ndigits, dest, K, neg, precision);
+	}
+
+	/* write decimal w/o scientific notation */
+	if (!scientific || (K < 0 && (K > -7 || exp < 4))) {
+		return emit_fixed_digits (digits, ndigits, dest, K, neg, precision, exp);
+	}
+
+	return emit_scientific_digits (digits, ndigits, dest, K, neg, precision, exp);
+}
+
+static int filter_special (double fp, char *dest, unsigned precision)
+{
+	int nchars = 3;
+	char *d = dest;
+
+	if (fp == 0.0) {
+		if (get_dbits (fp) & signmask) {
+			*d++ = '-';
+			*d++ = '0';
+		}
+		else {
+			*d++ = '0';
+		}
+
+		if (precision) {
+			*d ++ = '.';
+			memset (d, '0', precision);
+		}
+
+		return d - dest + precision;
+	}
+
+	uint64_t bits = get_dbits (fp);
+
+	bool nan = (bits & expmask) == expmask;
+
+	if (!nan) {
+		return 0;
+	}
+
+	if (bits & fracmask) {
+		dest[0] = 'n';
+		dest[1] = 'a';
+		dest[2] = 'n';
+	}
+	else {
+		if (get_dbits (fp) & signmask) {
+			dest[0] = '-';
+			dest[1] = 'i';
+			dest[2] = 'n';
+			dest[3] = 'f';
+			nchars = 4;
+		}
+		else {
+			dest[0] = 'i';
+			dest[1] = 'n';
+			dest[2] = 'f';
+		}
+	}
+
+	return nchars;
+}
+
+int
+fpconv_dtoa (double d, char dest[FPCONV_BUFLEN],
+			 unsigned precision, bool scientific)
+{
+	char digits[18];
+
+	int str_len = 0;
+	bool neg = false;
+
+	if (precision > FPCONV_BUFLEN - 5) {
+		precision = FPCONV_BUFLEN - 5;
+	}
+
+	int spec = filter_special (d, dest, precision);
+
+	if (spec) {
+		return spec;
+	}
+
+	if (get_dbits (d) & signmask) {
+		dest[0] = '-';
+		str_len++;
+		neg = true;
+	}
+
+	int K = 0;
+	int ndigits = grisu2 (d, digits, &K);
+
+	str_len += emit_digits (digits, ndigits, dest + str_len, K, neg, precision,
+			scientific);
+
+	return str_len;
+}
diff --git a/contrib/fpconv/fpconv.h b/contrib/fpconv/fpconv.h
new file mode 100644
index 0000000..8c07c13
--- /dev/null
+++ b/contrib/fpconv/fpconv.h
@@ -0,0 +1,35 @@
+#ifndef FPCONV_H
+#define FPCONV_H
+
+#define FPCONV_BUFLEN 32
+/* Fast and accurate double to string conversion based on Florian Loitsch's
+ * Grisu-algorithm[1].
+ *
+ * Input:
+ * fp -> the double to convert, dest -> destination buffer.
+ * The generated string will never be longer than 24 characters.
+ * Make sure to pass a pointer to at least 24 bytes of memory.
+ * The emitted string will not be null terminated.
+ *
+ * Output:
+ * The number of written characters.
+ *
+ * Exemplary usage:
+ *
+ * void print(double d)
+ * {
+ *      char buf[24 + 1] // plus null terminator
+ *      int str_len = fpconv_dtoa(d, buf);
+ *
+ *      buf[str_len] = '\0';
+ *      printf("%s", buf);
+ * }
+ *
+ */
+
+int fpconv_dtoa(double fp, char dest[FPCONV_BUFLEN], unsigned precision,
+		bool scientific);
+
+#endif
+
+/* [1] http://florian.loitsch.com/publications/dtoa-pldi2010.pdf */
diff --git a/contrib/fpconv/powers.h b/contrib/fpconv/powers.h
new file mode 100644
index 0000000..c707eed
--- /dev/null
+++ b/contrib/fpconv/powers.h
@@ -0,0 +1,87 @@
+#include <stdint.h>
+
+#define npowers     87
+#define steppowers  8
+#define firstpower -348 /* 10 ^ -348 */
+
+#define expmax     -32
+#define expmin     -60
+
+
+typedef struct Fp {
+    uint64_t frac;
+    int exp;
+} Fp;
+
+static Fp powers_ten[] = {
+    { 18054884314459144840U, -1220 }, { 13451937075301367670U, -1193 },
+    { 10022474136428063862U, -1166 }, { 14934650266808366570U, -1140 },
+    { 11127181549972568877U, -1113 }, { 16580792590934885855U, -1087 },
+    { 12353653155963782858U, -1060 }, { 18408377700990114895U, -1034 },
+    { 13715310171984221708U, -1007 }, { 10218702384817765436U, -980 },
+    { 15227053142812498563U, -954 },  { 11345038669416679861U, -927 },
+    { 16905424996341287883U, -901 },  { 12595523146049147757U, -874 },
+    { 9384396036005875287U,  -847 },  { 13983839803942852151U, -821 },
+    { 10418772551374772303U, -794 },  { 15525180923007089351U, -768 },
+    { 11567161174868858868U, -741 },  { 17236413322193710309U, -715 },
+    { 12842128665889583758U, -688 },  { 9568131466127621947U,  -661 },
+    { 14257626930069360058U, -635 },  { 10622759856335341974U, -608 },
+    { 15829145694278690180U, -582 },  { 11793632577567316726U, -555 },
+    { 17573882009934360870U, -529 },  { 13093562431584567480U, -502 },
+    { 9755464219737475723U,  -475 },  { 14536774485912137811U, -449 },
+    { 10830740992659433045U, -422 },  { 16139061738043178685U, -396 },
+    { 12024538023802026127U, -369 },  { 17917957937422433684U, -343 },
+    { 13349918974505688015U, -316 },  { 9946464728195732843U,  -289 },
+    { 14821387422376473014U, -263 },  { 11042794154864902060U, -236 },
+    { 16455045573212060422U, -210 },  { 12259964326927110867U, -183 },
+    { 18268770466636286478U, -157 },  { 13611294676837538539U, -130 },
+    { 10141204801825835212U, -103 },  { 15111572745182864684U, -77 },
+    { 11258999068426240000U, -50 },   { 16777216000000000000U, -24 },
+    { 12500000000000000000U,   3 },   { 9313225746154785156U,   30 },
+    { 13877787807814456755U,  56 },   { 10339757656912845936U,  83 },
+    { 15407439555097886824U, 109 },   { 11479437019748901445U, 136 },
+    { 17105694144590052135U, 162 },   { 12744735289059618216U, 189 },
+    { 9495567745759798747U,  216 },   { 14149498560666738074U, 242 },
+    { 10542197943230523224U, 269 },   { 15709099088952724970U, 295 },
+    { 11704190886730495818U, 322 },   { 17440603504673385349U, 348 },
+    { 12994262207056124023U, 375 },   { 9681479787123295682U,  402 },
+    { 14426529090290212157U, 428 },   { 10748601772107342003U, 455 },
+    { 16016664761464807395U, 481 },   { 11933345169920330789U, 508 },
+    { 17782069995880619868U, 534 },   { 13248674568444952270U, 561 },
+    { 9871031767461413346U,  588 },   { 14708983551653345445U, 614 },
+    { 10959046745042015199U, 641 },   { 16330252207878254650U, 667 },
+    { 12166986024289022870U, 694 },   { 18130221999122236476U, 720 },
+    { 13508068024458167312U, 747 },   { 10064294952495520794U, 774 },
+    { 14996968138956309548U, 800 },   { 11173611982879273257U, 827 },
+    { 16649979327439178909U, 853 },   { 12405201291620119593U, 880 },
+    { 9242595204427927429U,  907 },   { 13772540099066387757U, 933 },
+    { 10261342003245940623U, 960 },   { 15290591125556738113U, 986 },
+    { 11392378155556871081U, 1013 },  { 16975966327722178521U, 1039 },
+    { 12648080533535911531U, 1066 }
+};
+
+static Fp find_cachedpow10(int exp, int* k)
+{
+    const double one_log_ten = 0.30102999566398114;
+
+    int approx = -(exp + npowers) * one_log_ten;
+    int idx = (approx - firstpower) / steppowers;
+
+    while(1) {
+        int current = exp + powers_ten[idx].exp + 64;
+
+        if(current < expmin) {
+            idx++;
+            continue;
+        }
+
+        if(current > expmax) {
+            idx--;
+            continue;
+        }
+
+        *k = (firstpower + idx * steppowers);
+
+        return powers_ten[idx];
+    }
+}