The Tor Browser / file comparison

comparison: dom/indexedDB/Key.cpp

dom/indexedDB/Key.cpp

branch
TOR_BUG_9701
changeset 15
b8a032363ba2
equal deleted inserted replaced
-1:000000000000 0:822745a1c54b
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "mozilla/FloatingPoint.h"
8
9 #include "Key.h"
10 #include "ReportInternalError.h"
11
12 #include "jsfriendapi.h"
13 #include "nsAlgorithm.h"
14 #include "nsJSUtils.h"
15 #include "xpcpublic.h"
16 #include "mozilla/Endian.h"
17 #include <algorithm>
18
19 USING_INDEXEDDB_NAMESPACE
20
21 /*
22 Here's how we encode keys:
23
24 Basic strategy is the following
25
26 Numbers: 1 n n n n n n n n ("n"s are encoded 64bit float)
27 Dates: 2 n n n n n n n n ("n"s are encoded 64bit float)
28 Strings: 3 s s s ... 0 ("s"s are encoded unicode bytes)
29 Arrays: 4 i i i ... 0 ("i"s are encoded array items)
30
31
32 When encoding floats, 64bit IEEE 754 are almost sortable, except that
33 positive sort lower than negative, and negative sort descending. So we use
34 the following encoding:
35
36 value < 0 ?
37 (-to64bitInt(value)) :
38 (to64bitInt(value) | 0x8000000000000000)
39
40
41 When encoding strings, we use variable-size encoding per the following table
42
43 Chars 0 - 7E are encoded as 0xxxxxxx with 1 added
44 Chars 7F - (3FFF+7F) are encoded as 10xxxxxx xxxxxxxx with 7F subtracted
45 Chars (3FFF+80) - FFFF are encoded as 11xxxxxx xxxxxxxx xx000000
46
47 This ensures that the first byte is never encoded as 0, which means that the
48 string terminator (per basic-stategy table) sorts before any character.
49 The reason that (3FFF+80) - FFFF is encoded "shifted up" 6 bits is to maximize
50 the chance that the last character is 0. See below for why.
51
52
53 When encoding Arrays, we use an additional trick. Rather than adding a byte
54 containing the value '4' to indicate type, we instead add 4 to the next byte.
55 This is usually the byte containing the type of the first item in the array.
56 So simple examples are
57
58 ["foo"] 7 s s s 0 0 // 7 is 3 + 4
59 [1, 2] 5 n n n n n n n n 1 n n n n n n n n 0 // 5 is 1 + 4
60
61 Whe do this iteratively if the first item in the array is also an array
62
63 [["foo"]] 11 s s s 0 0 0
64
65 However, to avoid overflow in the byte, we only do this 3 times. If the first
66 item in an array is an array, and that array also has an array as first item,
67 we simply write out the total value accumulated so far and then follow the
68 "normal" rules.
69
70 [[["foo"]]] 12 3 s s s 0 0 0 0
71
72 There is another edge case that can happen though, which is that the array
73 doesn't have a first item to which we can add 4 to the type. Instead the
74 next byte would normally be the array terminator (per basic-strategy table)
75 so we simply add the 4 there.
76
77 [[]] 8 0 // 8 is 4 + 4 + 0
78 [] 4 // 4 is 4 + 0
79 [[], "foo"] 8 3 s s s 0 0 // 8 is 4 + 4 + 0
80
81 Note that the max-3-times rule kicks in before we get a chance to add to the
82 array terminator
83
84 [[[]]] 12 0 0 0 // 12 is 4 + 4 + 4
85
86 We could use a much higher number than 3 at no complexity or performance cost,
87 however it seems unlikely that it'll make a practical difference, and the low
88 limit makes testing eaiser.
89
90
91 As a final optimization we do a post-encoding step which drops all 0s at the
92 end of the encoded buffer.
93
94 "foo" // 3 s s s
95 1 // 1 bf f0
96 ["a", "b"] // 7 s 3 s
97 [1, 2] // 5 bf f0 0 0 0 0 0 0 1 c0
98 [[]] // 8
99 */
100
101 const int MaxArrayCollapse = 3;
102
103 const int MaxRecursionDepth = 256;
104
105 nsresult
106 Key::EncodeJSValInternal(JSContext* aCx, JS::Handle<JS::Value> aVal,
107 uint8_t aTypeOffset, uint16_t aRecursionDepth)
108 {
109 NS_ENSURE_TRUE(aRecursionDepth < MaxRecursionDepth, NS_ERROR_DOM_INDEXEDDB_DATA_ERR);
110
111 static_assert(eMaxType * MaxArrayCollapse < 256,
112 "Unable to encode jsvals.");
113
114 if (aVal.isString()) {
115 nsDependentJSString str;
116 if (!str.init(aCx, aVal)) {
117 IDB_REPORT_INTERNAL_ERR();
118 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
119 }
120 EncodeString(str, aTypeOffset);
121 return NS_OK;
122 }
123
124 if (aVal.isNumber()) {
125 double d = aVal.toNumber();
126 if (mozilla::IsNaN(d)) {
127 return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
128 }
129 EncodeNumber(d, eFloat + aTypeOffset);
130 return NS_OK;
131 }
132
133 if (aVal.isObject()) {
134 JS::Rooted<JSObject*> obj(aCx, &aVal.toObject());
135 if (JS_IsArrayObject(aCx, obj)) {
136 aTypeOffset += eMaxType;
137
138 if (aTypeOffset == eMaxType * MaxArrayCollapse) {
139 mBuffer.Append(aTypeOffset);
140 aTypeOffset = 0;
141 }
142 NS_ASSERTION((aTypeOffset % eMaxType) == 0 &&
143 aTypeOffset < (eMaxType * MaxArrayCollapse),
144 "Wrong typeoffset");
145
146 uint32_t length;
147 if (!JS_GetArrayLength(aCx, obj, &length)) {
148 IDB_REPORT_INTERNAL_ERR();
149 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
150 }
151
152 for (uint32_t index = 0; index < length; index++) {
153 JS::Rooted<JS::Value> val(aCx);
154 if (!JS_GetElement(aCx, obj, index, &val)) {
155 IDB_REPORT_INTERNAL_ERR();
156 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
157 }
158
159 nsresult rv = EncodeJSValInternal(aCx, val, aTypeOffset,
160 aRecursionDepth + 1);
161 if (NS_FAILED(rv)) {
162 return rv;
163 }
164
165 aTypeOffset = 0;
166 }
167
168 mBuffer.Append(eTerminator + aTypeOffset);
169
170 return NS_OK;
171 }
172
173 if (JS_ObjectIsDate(aCx, obj)) {
174 if (!js_DateIsValid(obj)) {
175 return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
176 }
177 EncodeNumber(js_DateGetMsecSinceEpoch(obj), eDate + aTypeOffset);
178 return NS_OK;
179 }
180 }
181
182 return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
183 }
184
185 // static
186 nsresult
187 Key::DecodeJSValInternal(const unsigned char*& aPos, const unsigned char* aEnd,
188 JSContext* aCx, uint8_t aTypeOffset, JS::MutableHandle<JS::Value> aVal,
189 uint16_t aRecursionDepth)
190 {
191 NS_ENSURE_TRUE(aRecursionDepth < MaxRecursionDepth, NS_ERROR_DOM_INDEXEDDB_DATA_ERR);
192
193 if (*aPos - aTypeOffset >= eArray) {
194 JS::Rooted<JSObject*> array(aCx, JS_NewArrayObject(aCx, 0));
195 if (!array) {
196 NS_WARNING("Failed to make array!");
197 IDB_REPORT_INTERNAL_ERR();
198 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
199 }
200
201 aTypeOffset += eMaxType;
202
203 if (aTypeOffset == eMaxType * MaxArrayCollapse) {
204 ++aPos;
205 aTypeOffset = 0;
206 }
207
208 uint32_t index = 0;
209 JS::Rooted<JS::Value> val(aCx);
210 while (aPos < aEnd && *aPos - aTypeOffset != eTerminator) {
211 nsresult rv = DecodeJSValInternal(aPos, aEnd, aCx, aTypeOffset,
212 &val, aRecursionDepth + 1);
213 NS_ENSURE_SUCCESS(rv, rv);
214
215 aTypeOffset = 0;
216
217 if (!JS_SetElement(aCx, array, index++, val)) {
218 NS_WARNING("Failed to set array element!");
219 IDB_REPORT_INTERNAL_ERR();
220 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
221 }
222 }
223
224 NS_ASSERTION(aPos >= aEnd || (*aPos % eMaxType) == eTerminator,
225 "Should have found end-of-array marker");
226 ++aPos;
227
228 aVal.setObject(*array);
229 }
230 else if (*aPos - aTypeOffset == eString) {
231 nsString key;
232 DecodeString(aPos, aEnd, key);
233 if (!xpc::StringToJsval(aCx, key, aVal)) {
234 IDB_REPORT_INTERNAL_ERR();
235 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
236 }
237 }
238 else if (*aPos - aTypeOffset == eDate) {
239 double msec = static_cast<double>(DecodeNumber(aPos, aEnd));
240 JSObject* date = JS_NewDateObjectMsec(aCx, msec);
241 if (!date) {
242 IDB_WARNING("Failed to make date!");
243 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
244 }
245
246 aVal.setObject(*date);
247 }
248 else if (*aPos - aTypeOffset == eFloat) {
249 aVal.setDouble(DecodeNumber(aPos, aEnd));
250 }
251 else {
252 NS_NOTREACHED("Unknown key type!");
253 }
254
255 return NS_OK;
256 }
257
258 #define ONE_BYTE_LIMIT 0x7E
259 #define TWO_BYTE_LIMIT (0x3FFF+0x7F)
260
261 #define ONE_BYTE_ADJUST 1
262 #define TWO_BYTE_ADJUST (-0x7F)
263 #define THREE_BYTE_SHIFT 6
264
265 void
266 Key::EncodeString(const nsAString& aString, uint8_t aTypeOffset)
267 {
268 // First measure how long the encoded string will be.
269
270 // The +2 is for initial 3 and trailing 0. We'll compensate for multi-byte
271 // chars below.
272 uint32_t size = aString.Length() + 2;
273
274 const char16_t* start = aString.BeginReading();
275 const char16_t* end = aString.EndReading();
276 for (const char16_t* iter = start; iter < end; ++iter) {
277 if (*iter > ONE_BYTE_LIMIT) {
278 size += *iter > TWO_BYTE_LIMIT ? 2 : 1;
279 }
280 }
281
282 // Allocate memory for the new size
283 uint32_t oldLen = mBuffer.Length();
284 char* buffer;
285 if (!mBuffer.GetMutableData(&buffer, oldLen + size)) {
286 return;
287 }
288 buffer += oldLen;
289
290 // Write type marker
291 *(buffer++) = eString + aTypeOffset;
292
293 // Encode string
294 for (const char16_t* iter = start; iter < end; ++iter) {
295 if (*iter <= ONE_BYTE_LIMIT) {
296 *(buffer++) = *iter + ONE_BYTE_ADJUST;
297 }
298 else if (*iter <= TWO_BYTE_LIMIT) {
299 char16_t c = char16_t(*iter) + TWO_BYTE_ADJUST + 0x8000;
300 *(buffer++) = (char)(c >> 8);
301 *(buffer++) = (char)(c & 0xFF);
302 }
303 else {
304 uint32_t c = (uint32_t(*iter) << THREE_BYTE_SHIFT) | 0x00C00000;
305 *(buffer++) = (char)(c >> 16);
306 *(buffer++) = (char)(c >> 8);
307 *(buffer++) = (char)c;
308 }
309 }
310
311 // Write end marker
312 *(buffer++) = eTerminator;
313
314 NS_ASSERTION(buffer == mBuffer.EndReading(), "Wrote wrong number of bytes");
315 }
316
317 // static
318 void
319 Key::DecodeString(const unsigned char*& aPos, const unsigned char* aEnd,
320 nsString& aString)
321 {
322 NS_ASSERTION(*aPos % eMaxType == eString, "Don't call me!");
323
324 const unsigned char* buffer = aPos + 1;
325
326 // First measure how big the decoded string will be.
327 uint32_t size = 0;
328 const unsigned char* iter;
329 for (iter = buffer; iter < aEnd && *iter != eTerminator; ++iter) {
330 if (*iter & 0x80) {
331 iter += (*iter & 0x40) ? 2 : 1;
332 }
333 ++size;
334 }
335
336 // Set end so that we don't have to check for null termination in the loop
337 // below
338 if (iter < aEnd) {
339 aEnd = iter;
340 }
341
342 char16_t* out;
343 if (size && !aString.GetMutableData(&out, size)) {
344 return;
345 }
346
347 for (iter = buffer; iter < aEnd;) {
348 if (!(*iter & 0x80)) {
349 *out = *(iter++) - ONE_BYTE_ADJUST;
350 }
351 else if (!(*iter & 0x40)) {
352 char16_t c = (char16_t(*(iter++)) << 8);
353 if (iter < aEnd) {
354 c |= *(iter++);
355 }
356 *out = c - TWO_BYTE_ADJUST - 0x8000;
357 }
358 else {
359 uint32_t c = uint32_t(*(iter++)) << (16 - THREE_BYTE_SHIFT);
360 if (iter < aEnd) {
361 c |= uint32_t(*(iter++)) << (8 - THREE_BYTE_SHIFT);
362 }
363 if (iter < aEnd) {
364 c |= *(iter++) >> THREE_BYTE_SHIFT;
365 }
366 *out = (char16_t)c;
367 }
368
369 ++out;
370 }
371
372 NS_ASSERTION(!size || out == aString.EndReading(),
373 "Should have written the whole string");
374
375 aPos = iter + 1;
376 }
377
378 union Float64Union {
379 double d;
380 uint64_t u;
381 };
382
383 void
384 Key::EncodeNumber(double aFloat, uint8_t aType)
385 {
386 // Allocate memory for the new size
387 uint32_t oldLen = mBuffer.Length();
388 char* buffer;
389 if (!mBuffer.GetMutableData(&buffer, oldLen + 1 + sizeof(double))) {
390 return;
391 }
392 buffer += oldLen;
393
394 *(buffer++) = aType;
395
396 Float64Union pun;
397 pun.d = aFloat;
398 // Note: The subtraction from 0 below is necessary to fix
399 // MSVC build warning C4146 (negating an unsigned value).
400 uint64_t number = pun.u & PR_UINT64(0x8000000000000000) ?
401 (0 - pun.u) :
402 (pun.u | PR_UINT64(0x8000000000000000));
403
404 mozilla::BigEndian::writeUint64(buffer, number);
405 }
406
407 // static
408 double
409 Key::DecodeNumber(const unsigned char*& aPos, const unsigned char* aEnd)
410 {
411 NS_ASSERTION(*aPos % eMaxType == eFloat ||
412 *aPos % eMaxType == eDate, "Don't call me!");
413
414 ++aPos;
415
416 uint64_t number = 0;
417 memcpy(&number, aPos, std::min<size_t>(sizeof(number), aEnd - aPos));
418 number = mozilla::NativeEndian::swapFromBigEndian(number);
419
420 aPos += sizeof(number);
421
422 Float64Union pun;
423 // Note: The subtraction from 0 below is necessary to fix
424 // MSVC build warning C4146 (negating an unsigned value).
425 pun.u = number & PR_UINT64(0x8000000000000000) ?
426 (number & ~PR_UINT64(0x8000000000000000)) :
427 (0 - number);
428
429 return pun.d;
430 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial