3998645281

Build Type

github

Committed by GitHub

Commit Message

Merge b1e3c924b into 5a28b6413

Pull Request Pull Request #148: use separate namespace for xxh functions

Run Details

0 of 5107 relevant lines covered (0.0%)

0.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/src/fpconv.cpp

/* 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);
 * }
 *
 * [1] http://florian.loitsch.com/publications/dtoa-pldi2010.pdf
 */

#include <cstring>

#include "velocypack/velocypack-common.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))

namespace arangodb::velocypack {
// forward for fpconv function
int fpconv_dtoa(double fp, char dest[24]);
}  // namespace arangodb::velocypack

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) {
  uint64_t r;
  std::memcpy(&r, &d, sizeof(uint64_t));
  return r;
}

static Fp build_fp(double d) {
  uint64_t bits = get_dbits(d);

  Fp fp;
  fp.frac = bits & fracmask;
  fp.exp = (bits & expmask) >> 52;

  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 <<= 1;
    fp->exp--;
  }

  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 << 1) + 1;
  upper->exp = fp->exp - 1;

  while ((upper->frac & (hiddenbit << 1)) == 0) {
    upper->frac <<= 1;
    upper->exp--;
  }

  int u_shift = 64 - 52 - 2;

  upper->frac <<= u_shift;
  upper->exp = upper->exp - u_shift;

  int l_shift = fp->frac == hiddenbit ? 2 : 1;

  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 = 0x00000000FFFFFFFF;

  uint64_t ah_bl = (a->frac >> 32) * (b->frac & lomask);
  uint64_t al_bh = (a->frac & lomask) * (b->frac >> 32);
  uint64_t al_bl = (a->frac & lomask) * (b->frac & lomask);
  uint64_t ah_bh = (a->frac >> 32) * (b->frac >> 32);

  uint64_t tmp = (ah_bl & lomask) + (al_bh & lomask) + (al_bl >> 32);
  /* round up */
  tmp += 1U << 31;

  Fp fp = {ah_bh + (ah_bl >> 32) + (al_bh >> 32) + (tmp >> 32),
           a->exp + b->exp + 64};

  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 = static_cast<unsigned>(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 = static_cast<unsigned>(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 int emit_digits(char* digits, int ndigits, char* dest, int K, bool neg) {
  int exp = absv(K + ndigits - 1);

  /* write plain integer */
  if (K >= 0 && (exp < (ndigits + 7))) {
    memcpy(dest, digits, ndigits);
    // intentionally fill with '0', not 0 (NUL byte) because
    // we want the string representation of the number zero
    memset(dest + ndigits, '0', K);

    return ndigits + K;
  }

  /* write decimal w/o scientific notation */
  if (K < 0 && (K > -7 || exp < 4)) {
    int offset = ndigits - absv(K);
    /* fp < 1.0 -> write leading zero */
    if (offset <= 0) {
      offset = -offset;
      dest[0] = '0';
      dest[1] = '.';
      memset(dest + 2, '0', offset);
      memcpy(dest + offset + 2, digits, ndigits);

      return ndigits + 2 + offset;

      /* fp > 1.0 */
    } else {
      memcpy(dest, digits, offset);
      dest[offset] = '.';
      memcpy(dest + offset + 1, digits + offset, ndigits - offset);

      return ndigits + 1;
    }
  }

  /* 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 int filter_special(double fp, char* dest) {
  if (fp == 0.0) {
    dest[0] = '0';
    return 1;
  }

  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 {
    dest[0] = 'i';
    dest[1] = 'n';
    dest[2] = 'f';
  }

  return 3;
}

int arangodb::velocypack::fpconv_dtoa(double d, char dest[24]) {
  char digits[18];

  int str_len = 0;
  bool neg = false;

  if (get_dbits(d) & signmask) {
    dest[0] = '-';
    str_len++;
    neg = true;
  }

  int spec = filter_special(d, dest + str_len);

  if (spec) {
    return str_len + spec;
  }

  // initialize digits[0] to satisfy scan_build
  digits[0] = '\0';

  int K = 0;
  int ndigits = grisu2(d, digits, &K);

  str_len += emit_digits(digits, ndigits, dest + str_len, K, neg);

  return str_len;
}

1	/* Fast and accurate double to string conversion based on Florian Loitsch's
2	* Grisu-algorithm[1].
3	*
4	* Input:
5	* fp -> the double to convert, dest -> destination buffer.
6	* The generated string will never be longer than 24 characters.
7	* Make sure to pass a pointer to at least 24 bytes of memory.
8	* The emitted string will not be null terminated.
9	*
10	* Output:
11	* The number of written characters.
12	*
13	* Exemplary usage:
14	*
15	* void print(double d)
16	* {
17	* char buf[24 + 1] // plus null terminator
18	* int str_len = fpconv_dtoa(d, buf);
19	*
20	* buf[str_len] = '\0';
21	* printf("%s", buf);
22	* }
23	*
24	* [1] http://florian.loitsch.com/publications/dtoa-pldi2010.pdf
25	*/
26
27	#include <cstring>
28
29	#include "velocypack/velocypack-common.h"
30	#include "powers.h"
31
32	#define fracmask 0x000FFFFFFFFFFFFFU
33	#define expmask 0x7FF0000000000000U
34	#define hiddenbit 0x0010000000000000U
35	#define signmask 0x8000000000000000U
36	#define expbias (1023 + 52)
37
38	#define absv(n) ((n) < 0 ? -(n) : (n))
39	#define minv(a, b) ((a) < (b) ? (a) : (b))
40
41	namespace arangodb::velocypack {
42	// forward for fpconv function
43	int fpconv_dtoa(double fp, char dest[24]);
44	} // namespace arangodb::velocypack
45
46	static uint64_t tens[] = {10000000000000000000U,
47	1000000000000000000U,
48	100000000000000000U,
49	10000000000000000U,
50	1000000000000000U,
51	100000000000000U,
52	10000000000000U,
53	1000000000000U,
54	100000000000U,
55	10000000000U,
56	1000000000U,
57	100000000U,
58	10000000U,
59	1000000U,
60	100000U,
61	10000U,
62	1000U,
63	100U,
64	10U,
65	1U};
66
67	static inline uint64_t get_dbits(double d) {	×
68	uint64_t r;
69	std::memcpy(&r, &d, sizeof(uint64_t));	×
70	return r;	×
71	}
72
73	static Fp build_fp(double d) {	×
74	uint64_t bits = get_dbits(d);	×
75
76	Fp fp;
77	fp.frac = bits & fracmask;	×
78	fp.exp = (bits & expmask) >> 52;	×
79
80	if (fp.exp) {	×
81	fp.frac += hiddenbit;	×
82	fp.exp -= expbias;	×
83
84	} else {
85	fp.exp = -expbias + 1;	×
86	}
87
88	return fp;	×
89	}
90
91	static void normalize(Fp* fp) {	×
92	while ((fp->frac & hiddenbit) == 0) {	×
93	fp->frac <<= 1;	×
94	fp->exp--;	×
95	}
96
97	int shift = 64 - 52 - 1;	×
98	fp->frac <<= shift;	×
99	fp->exp -= shift;	×
100	}	×
101
102	static void get_normalized_boundaries(Fp* fp, Fp* lower, Fp* upper) {	×
103	upper->frac = (fp->frac << 1) + 1;	×
104	upper->exp = fp->exp - 1;	×
105
106	while ((upper->frac & (hiddenbit << 1)) == 0) {	×
107	upper->frac <<= 1;	×
108	upper->exp--;	×
109	}
110
111	int u_shift = 64 - 52 - 2;	×
112
113	upper->frac <<= u_shift;	×
114	upper->exp = upper->exp - u_shift;	×
115
116	int l_shift = fp->frac == hiddenbit ? 2 : 1;	×
117
118	lower->frac = (fp->frac << l_shift) - 1;	×
119	lower->exp = fp->exp - l_shift;	×
120
121	lower->frac <<= lower->exp - upper->exp;	×
122	lower->exp = upper->exp;	×
123	}	×
124
125	static Fp multiply(Fp* a, Fp* b) {	×
126	const uint64_t lomask = 0x00000000FFFFFFFF;	×
127
128	uint64_t ah_bl = (a->frac >> 32) * (b->frac & lomask);	×
129	uint64_t al_bh = (a->frac & lomask) * (b->frac >> 32);	×
130	uint64_t al_bl = (a->frac & lomask) * (b->frac & lomask);	×
131	uint64_t ah_bh = (a->frac >> 32) * (b->frac >> 32);	×
132
133	uint64_t tmp = (ah_bl & lomask) + (al_bh & lomask) + (al_bl >> 32);	×
134	/* round up */
135	tmp += 1U << 31;	×
136
137	Fp fp = {ah_bh + (ah_bl >> 32) + (al_bh >> 32) + (tmp >> 32),	×
138	a->exp + b->exp + 64};	×
139
140	return fp;	×
141	}
142
143	static void round_digit(char* digits, int ndigits, uint64_t delta, uint64_t rem,	×
144	uint64_t kappa, uint64_t frac) {
145	while (rem < frac && delta - rem >= kappa &&	×
146	(rem + kappa < frac \|\| frac - rem > rem + kappa - frac)) {	×
147	digits[ndigits - 1]--;	×
148	rem += kappa;	×
149	}
150	}	×
151
152	static int generate_digits(Fp* fp, Fp* upper, Fp* lower, char* digits, int* K) {	×
153	uint64_t wfrac = upper->frac - fp->frac;	×
154	uint64_t delta = upper->frac - lower->frac;	×
155
156	Fp one;
157	one.frac = 1ULL << -upper->exp;	×
158	one.exp = upper->exp;	×
159
160	uint64_t part1 = upper->frac >> -one.exp;	×
161	uint64_t part2 = upper->frac & (one.frac - 1);	×
162
163	int idx = 0, kappa = 10;	×
164	uint64_t* divp;
165	/* 1000000000 */
166	for (divp = tens + 10; kappa > 0; divp++) {	×
167	uint64_t div = *divp;	×
168	unsigned digit = static_cast<unsigned>(part1 / div);	×
169
170	if (digit \|\| idx) {	×
171	digits[idx++] = digit + '0';	×
172	}
173
174	part1 -= digit * div;	×
175	kappa--;	×
176
177	uint64_t tmp = (part1 << -one.exp) + part2;	×
178	if (tmp <= delta) {	×
179	*K += kappa;	×
180	round_digit(digits, idx, delta, tmp, div << -one.exp, wfrac);	×
181
182	return idx;	×
183	}
184	}
185
186	/* 10 */
187	uint64_t* unit = tens + 18;	×
188
189	while (true) {
190	part2 *= 10;	×
191	delta *= 10;	×
192	kappa--;	×
193
194	unsigned digit = static_cast<unsigned>(part2 >> -one.exp);	×
195	if (digit \|\| idx) {	×
196	digits[idx++] = digit + '0';	×
197	}
198
199	part2 &= one.frac - 1;	×
200	if (part2 < delta) {	×
201	*K += kappa;	×
202	round_digit(digits, idx, delta, part2, one.frac, wfrac * *unit);	×
203
204	return idx;	×
205	}
206
207	unit--;	×
208	}	×
209	}
210
211	static int grisu2(double d, char* digits, int* K) {	×
212	Fp w = build_fp(d);	×
213
214	Fp lower, upper;
215	get_normalized_boundaries(&w, &lower, &upper);	×
216
217	normalize(&w);	×
218
219	int k;
220	Fp cp = find_cachedpow10(upper.exp, &k);	×
221
222	w = multiply(&w, &cp);	×
223	upper = multiply(&upper, &cp);	×
224	lower = multiply(&lower, &cp);	×
225
226	lower.frac++;	×
227	upper.frac--;	×
228
229	*K = -k;	×
230
231	return generate_digits(&w, &upper, &lower, digits, K);	×
232	}
233
234	static int emit_digits(char* digits, int ndigits, char* dest, int K, bool neg) {	×
235	int exp = absv(K + ndigits - 1);	×
236
237	/* write plain integer */
238	if (K >= 0 && (exp < (ndigits + 7))) {	×
239	memcpy(dest, digits, ndigits);	×
240	// intentionally fill with '0', not 0 (NUL byte) because
241	// we want the string representation of the number zero
242	memset(dest + ndigits, '0', K);	×
243
244	return ndigits + K;	×
245	}
246
247	/* write decimal w/o scientific notation */
248	if (K < 0 && (K > -7 \|\| exp < 4)) {	×
249	int offset = ndigits - absv(K);	×
250	/* fp < 1.0 -> write leading zero */
251	if (offset <= 0) {	×
252	offset = -offset;	×
253	dest[0] = '0';	×
254	dest[1] = '.';	×
255	memset(dest + 2, '0', offset);	×
256	memcpy(dest + offset + 2, digits, ndigits);	×
257
258	return ndigits + 2 + offset;	×
259
260	/* fp > 1.0 */
261	} else {
262	memcpy(dest, digits, offset);	×
263	dest[offset] = '.';	×
264	memcpy(dest + offset + 1, digits + offset, ndigits - offset);	×
265
266	return ndigits + 1;	×
267	}
268	}
269
270	/* write decimal w/ scientific notation */
271	ndigits = minv(ndigits, 18 - neg);	×
272
273	int idx = 0;	×
274	dest[idx++] = digits[0];	×
275
276	if (ndigits > 1) {	×
277	dest[idx++] = '.';	×
278	memcpy(dest + idx, digits + 1, ndigits - 1);	×
279	idx += ndigits - 1;	×
280	}
281
282	dest[idx++] = 'e';	×
283
284	char sign = K + ndigits - 1 < 0 ? '-' : '+';	×
285	dest[idx++] = sign;	×
286
287	int cent = 0;	×
288
289	if (exp > 99) {	×
290	cent = exp / 100;	×
291	dest[idx++] = cent + '0';	×
292	exp -= cent * 100;	×
293	}
294	if (exp > 9) {	×
295	int dec = exp / 10;	×
296	dest[idx++] = dec + '0';	×
297	exp -= dec * 10;	×
298
299	} else if (cent) {	×
300	dest[idx++] = '0';	×
301	}
302
303	dest[idx++] = exp % 10 + '0';	×
304
305	return idx;	×
306	}
307
308	static int filter_special(double fp, char* dest) {	×
309	if (fp == 0.0) {	×
310	dest[0] = '0';	×
311	return 1;	×
312	}
313
314	uint64_t bits = get_dbits(fp);	×
315
316	bool nan = (bits & expmask) == expmask;	×
317
318	if (!nan) {	×
319	return 0;	×
320	}
321
322	if (bits & fracmask) {	×
323	dest[0] = 'N';	×
324	dest[1] = 'a';	×
325	dest[2] = 'N';	×
326
327	} else {
328	dest[0] = 'i';	×
329	dest[1] = 'n';	×
330	dest[2] = 'f';	×
331	}
332
333	return 3;	×
334	}
335
336	int arangodb::velocypack::fpconv_dtoa(double d, char dest[24]) {	×
337	char digits[18];
338
339	int str_len = 0;	×
340	bool neg = false;	×
341
342	if (get_dbits(d) & signmask) {	×
343	dest[0] = '-';	×
344	str_len++;	×
345	neg = true;	×
346	}
347
348	int spec = filter_special(d, dest + str_len);	×
349
350	if (spec) {	×
351	return str_len + spec;	×
352	}
353
354	// initialize digits[0] to satisfy scan_build
355	digits[0] = '\0';	×
356
357	int K = 0;	×
358	int ndigits = grisu2(d, digits, &K);	×
359
360	str_len += emit_digits(digits, ndigits, dest + str_len, K, neg);	×
361
362	return str_len;	×
363	}

arangodb / velocypack / 3998645281

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous