dom/indexedDB/Key.cpp@6474c204b198
dom/indexedDB/Key.cpp
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
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/. */
7 #include "mozilla/FloatingPoint.h"
9 #include "Key.h"
10 #include "ReportInternalError.h"
12 #include "jsfriendapi.h"
13 #include "nsAlgorithm.h"
14 #include "nsJSUtils.h"
15 #include "xpcpublic.h"
16 #include "mozilla/Endian.h"
17 #include <algorithm>
19 USING_INDEXEDDB_NAMESPACE
21 /*
22 Here's how we encode keys:
24 Basic strategy is the following
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)
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:
36 value < 0 ?
37 (-to64bitInt(value)) :
38 (to64bitInt(value) | 0x8000000000000000)
41 When encoding strings, we use variable-size encoding per the following table
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
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.
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
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
61 Whe do this iteratively if the first item in the array is also an array
63 [["foo"]] 11 s s s 0 0 0
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.
70 [[["foo"]]] 12 3 s s s 0 0 0 0
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.
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
81 Note that the max-3-times rule kicks in before we get a chance to add to the
82 array terminator
84 [[[]]] 12 0 0 0 // 12 is 4 + 4 + 4
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.
91 As a final optimization we do a post-encoding step which drops all 0s at the
92 end of the encoded buffer.
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 */
101 const int MaxArrayCollapse = 3;
103 const int MaxRecursionDepth = 256;
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);
111 static_assert(eMaxType * MaxArrayCollapse < 256,
112 "Unable to encode jsvals.");
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 }
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 }
133 if (aVal.isObject()) {
134 JS::Rooted<JSObject*> obj(aCx, &aVal.toObject());
135 if (JS_IsArrayObject(aCx, obj)) {
136 aTypeOffset += eMaxType;
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");
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 }
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 }
159 nsresult rv = EncodeJSValInternal(aCx, val, aTypeOffset,
160 aRecursionDepth + 1);
161 if (NS_FAILED(rv)) {
162 return rv;
163 }
165 aTypeOffset = 0;
166 }
168 mBuffer.Append(eTerminator + aTypeOffset);
170 return NS_OK;
171 }
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 }
182 return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
183 }
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);
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 }
201 aTypeOffset += eMaxType;
203 if (aTypeOffset == eMaxType * MaxArrayCollapse) {
204 ++aPos;
205 aTypeOffset = 0;
206 }
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);
215 aTypeOffset = 0;
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 }
224 NS_ASSERTION(aPos >= aEnd || (*aPos % eMaxType) == eTerminator,
225 "Should have found end-of-array marker");
226 ++aPos;
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 }
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 }
255 return NS_OK;
256 }
258 #define ONE_BYTE_LIMIT 0x7E
259 #define TWO_BYTE_LIMIT (0x3FFF+0x7F)
261 #define ONE_BYTE_ADJUST 1
262 #define TWO_BYTE_ADJUST (-0x7F)
263 #define THREE_BYTE_SHIFT 6
265 void
266 Key::EncodeString(const nsAString& aString, uint8_t aTypeOffset)
267 {
268 // First measure how long the encoded string will be.
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;
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 }
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;
290 // Write type marker
291 *(buffer++) = eString + aTypeOffset;
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 }
311 // Write end marker
312 *(buffer++) = eTerminator;
314 NS_ASSERTION(buffer == mBuffer.EndReading(), "Wrote wrong number of bytes");
315 }
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!");
324 const unsigned char* buffer = aPos + 1;
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 }
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 }
342 char16_t* out;
343 if (size && !aString.GetMutableData(&out, size)) {
344 return;
345 }
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 }
369 ++out;
370 }
372 NS_ASSERTION(!size || out == aString.EndReading(),
373 "Should have written the whole string");
375 aPos = iter + 1;
376 }
378 union Float64Union {
379 double d;
380 uint64_t u;
381 };
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;
394 *(buffer++) = aType;
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));
404 mozilla::BigEndian::writeUint64(buffer, number);
405 }
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!");
414 ++aPos;
416 uint64_t number = 0;
417 memcpy(&number, aPos, std::min<size_t>(sizeof(number), aEnd - aPos));
418 number = mozilla::NativeEndian::swapFromBigEndian(number);
420 aPos += sizeof(number);
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);
429 return pun.d;
430 }
