Branch data Line data Source code
1 : : /* @file serialise-double.cc
2 : : * @brief functions to serialise and unserialise a double
3 : : */
4 : : /* Copyright (C) 2006,2007,2008,2009 Olly Betts
5 : : *
6 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
7 : : * of this software and associated documentation files (the "Software"), to
8 : : * deal in the Software without restriction, including without limitation the
9 : : * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 : : * sell copies of the Software, and to permit persons to whom the Software is
11 : : * furnished to do so, subject to the following conditions:
12 : : *
13 : : * The above copyright notice and this permission notice shall be included in
14 : : * all copies or substantial portions of the Software.
15 : : *
16 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 : : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 : : * IN THE SOFTWARE.
23 : : */
24 : :
25 : : #include <config.h>
26 : :
27 : : #include <xapian/error.h>
28 : :
29 : : #include "omassert.h"
30 : :
31 : : #include "serialise-double.h"
32 : :
33 : : #include <cfloat>
34 : : #include <cmath>
35 : :
36 : : #include <algorithm>
37 : : #include <string>
38 : :
39 : : using namespace std;
40 : :
41 : : // The serialisation we use for doubles is inspired by a comp.lang.c post
42 : : // by Jens Moeller:
43 : : //
44 : : // http://groups.google.com/group/comp.lang.c/browse_thread/thread/6558d4653f6dea8b/75a529ec03148c98
45 : : //
46 : : // The clever part is that the mantissa is encoded as a base-256 number which
47 : : // means there's no rounding error provided both ends have FLT_RADIX as some
48 : : // power of two.
49 : : //
50 : : // FLT_RADIX == 2 seems to be ubiquitous on modern UNIX platforms, while
51 : : // some older platforms used FLT_RADIX == 16 (IBM machines for example).
52 : : // FLT_RADIX == 10 seems to be very rare (the only instance Google finds
53 : : // is for a cross-compiler to some TI calculators).
54 : :
55 : : #if FLT_RADIX == 2
56 : : # define MAX_MANTISSA_BYTES ((DBL_MANT_DIG + 7 + 7) / 8)
57 : : # define MAX_EXP ((DBL_MAX_EXP + 1) / 8)
58 : : # define MAX_MANTISSA (1 << (DBL_MAX_EXP & 7))
59 : : #elif FLT_RADIX == 16
60 : : # define MAX_MANTISSA_BYTES ((DBL_MANT_DIG + 1 + 1) / 2)
61 : : # define MAX_EXP ((DBL_MAX_EXP + 1) / 2)
62 : : # define MAX_MANTISSA (1 << ((DBL_MAX_EXP & 1) * 4))
63 : : #else
64 : : # error FLT_RADIX is a value not currently handled (not 2 or 16)
65 : : // # define MAX_MANTISSA_BYTES (sizeof(double) + 1)
66 : : #endif
67 : :
68 : 84592 : static int base256ify_double(double &v) {
69 : : int exp;
70 : 84592 : v = frexp(v, &exp);
71 : : // v is now in the range [0.5, 1.0)
72 : 84592 : --exp;
73 : 84592 : v = ldexp(v, (exp & 7) + 1);
74 : : // v is now in the range [1.0, 256.0)
75 : 84592 : exp >>= 3;
76 : 84592 : return exp;
77 : : }
78 : :
79 : 83773 : std::string serialise_double(double v)
80 : : {
81 : : /* First byte:
82 : : * bit 7 Negative flag
83 : : * bit 4..6 Mantissa length - 1
84 : : * bit 0..3 --- 0-13 -> Exponent + 7
85 : : * \- 14 -> Exponent given by next byte
86 : : * - 15 -> Exponent given by next 2 bytes
87 : : *
88 : : * Then optional medium (1 byte) or large exponent (2 bytes, lsb first)
89 : : *
90 : : * Then mantissa (0 iff value is 0)
91 : : */
92 : :
93 : 83773 : bool negative = (v < 0.0);
94 : :
95 [ + + ]: 83773 : if (negative) v = -v;
96 : :
97 : 83773 : int exp = base256ify_double(v);
98 : :
99 : 83773 : string result;
100 : :
101 [ + + + + ]: 167508 : if (exp <= 6 && exp >= -7) {
102 : 83735 : unsigned char b = static_cast<unsigned char>(exp + 7);
103 [ + + ]: 83735 : if (negative) b |= static_cast<unsigned char>(0x80);
104 : 83735 : result += char(b);
105 : : } else {
106 [ + - ][ + + ]: 48 : if (exp >= -128 && exp < 127) {
107 [ + + ]: 10 : result += negative ? char(0x8e) : char(0x0e);
108 : 10 : result += char(exp + 128);
109 : : } else {
110 [ + - ][ - + ]: 28 : if (exp < -32768 || exp > 32767) {
111 : 0 : throw Xapian::InternalError("Insane exponent in floating point number");
112 : : }
113 [ + + ]: 28 : result += negative ? char(0x8f) : char(0x0f);
114 : 28 : result += char(unsigned(exp + 32768) & 0xff);
115 : 28 : result += char(unsigned(exp + 32768) >> 8);
116 : : }
117 : : }
118 : :
119 : 83773 : int maxbytes = min(MAX_MANTISSA_BYTES, 8);
120 : :
121 : 83773 : size_t n = result.size();
122 [ + + + - ]: 381868 : do {
[ + + ]
123 : 381868 : unsigned char byte = static_cast<unsigned char>(v);
124 : 381868 : result += char(byte);
125 : 381868 : v -= double(byte);
126 : 381868 : v *= 256.0;
127 : : } while (v != 0.0 && --maxbytes);
128 : :
129 : 83773 : n = result.size() - n;
130 [ + + ]: 83773 : if (n > 1) {
131 : : Assert(n <= 8);
132 : 83773 : result[0] = static_cast<unsigned char>(result[0] | ((n - 1) << 4));
133 : : }
134 : :
135 : 0 : return result;
136 : : }
137 : :
138 : 87293 : double unserialise_double(const char ** p, const char *end)
139 : : {
140 [ - + ]: 87293 : if (end - *p < 2) {
141 : 0 : throw Xapian::SerialisationError("Bad encoded double: insufficient data");
142 : : }
143 : 87293 : unsigned char first = *(*p)++;
144 [ - + ][ # # ]: 87293 : if (first == 0 && *(*p) == 0) {
145 : 0 : ++*p;
146 : 0 : return 0.0;
147 : : }
148 : :
149 : 87293 : bool negative = (first & 0x80) != 0;
150 : 87293 : size_t mantissa_len = ((first >> 4) & 0x07) + 1;
151 : :
152 : 87293 : int exp = first & 0x0f;
153 [ + + ]: 87293 : if (exp >= 14) {
154 : 38 : int bigexp = static_cast<unsigned char>(*(*p)++);
155 [ + + ]: 38 : if (exp == 15) {
156 [ - + ]: 28 : if (*p == end) {
157 : 0 : throw Xapian::SerialisationError("Bad encoded double: short large exponent");
158 : : }
159 : 28 : exp = bigexp | (static_cast<unsigned char>(*(*p)++) << 8);
160 : 28 : exp -= 32768;
161 : : } else {
162 : 10 : exp = bigexp - 128;
163 : : }
164 : : } else {
165 : 87255 : exp -= 7;
166 : : }
167 : :
168 [ - + ]: 87293 : if (size_t(end - *p) < mantissa_len) {
169 : 0 : throw Xapian::SerialisationError("Bad encoded double: short mantissa");
170 : : }
171 : :
172 : 87293 : double v = 0.0;
173 : :
174 : : static double dbl_max_mantissa = DBL_MAX;
175 [ + + ][ + - ]: 87293 : static int dbl_max_exp = base256ify_double(dbl_max_mantissa);
176 : 87293 : *p += mantissa_len;
177 [ + - ][ + + ]: 87293 : if (exp > dbl_max_exp ||
[ - + ]
178 : : (exp == dbl_max_exp && double(**p) > dbl_max_mantissa)) {
179 : : // The mantissa check should be precise provided that FLT_RADIX
180 : : // is a power of 2.
181 : 0 : v = HUGE_VAL;
182 : : } else {
183 : 87293 : const char *q = *p;
184 [ + + ]: 475408 : while (mantissa_len--) {
185 : 388115 : v *= 0.00390625; // 1/256
186 : 388115 : v += double(static_cast<unsigned char>(*--q));
187 : : }
188 : :
189 [ + + ]: 87293 : if (exp) v = ldexp(v, exp * 8);
190 : :
191 : : #if 0
192 : : if (v == 0.0) {
193 : : // FIXME: handle underflow
194 : : }
195 : : #endif
196 : : }
197 : :
198 [ + + ]: 87293 : if (negative) v = -v;
199 : :
200 : 87293 : return v;
201 : : }
|
