1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/dom/indexedDB/Key.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,430 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "mozilla/FloatingPoint.h"
1.11 +
1.12 +#include "Key.h"
1.13 +#include "ReportInternalError.h"
1.14 +
1.15 +#include "jsfriendapi.h"
1.16 +#include "nsAlgorithm.h"
1.17 +#include "nsJSUtils.h"
1.18 +#include "xpcpublic.h"
1.19 +#include "mozilla/Endian.h"
1.20 +#include <algorithm>
1.21 +
1.22 +USING_INDEXEDDB_NAMESPACE
1.23 +
1.24 +/*
1.25 + Here's how we encode keys:
1.26 +
1.27 + Basic strategy is the following
1.28 +
1.29 + Numbers: 1 n n n n n n n n ("n"s are encoded 64bit float)
1.30 + Dates: 2 n n n n n n n n ("n"s are encoded 64bit float)
1.31 + Strings: 3 s s s ... 0 ("s"s are encoded unicode bytes)
1.32 + Arrays: 4 i i i ... 0 ("i"s are encoded array items)
1.33 +
1.34 +
1.35 + When encoding floats, 64bit IEEE 754 are almost sortable, except that
1.36 + positive sort lower than negative, and negative sort descending. So we use
1.37 + the following encoding:
1.38 +
1.39 + value < 0 ?
1.40 + (-to64bitInt(value)) :
1.41 + (to64bitInt(value) | 0x8000000000000000)
1.42 +
1.43 +
1.44 + When encoding strings, we use variable-size encoding per the following table
1.45 +
1.46 + Chars 0 - 7E are encoded as 0xxxxxxx with 1 added
1.47 + Chars 7F - (3FFF+7F) are encoded as 10xxxxxx xxxxxxxx with 7F subtracted
1.48 + Chars (3FFF+80) - FFFF are encoded as 11xxxxxx xxxxxxxx xx000000
1.49 +
1.50 + This ensures that the first byte is never encoded as 0, which means that the
1.51 + string terminator (per basic-stategy table) sorts before any character.
1.52 + The reason that (3FFF+80) - FFFF is encoded "shifted up" 6 bits is to maximize
1.53 + the chance that the last character is 0. See below for why.
1.54 +
1.55 +
1.56 + When encoding Arrays, we use an additional trick. Rather than adding a byte
1.57 + containing the value '4' to indicate type, we instead add 4 to the next byte.
1.58 + This is usually the byte containing the type of the first item in the array.
1.59 + So simple examples are
1.60 +
1.61 + ["foo"] 7 s s s 0 0 // 7 is 3 + 4
1.62 + [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
1.63 +
1.64 + Whe do this iteratively if the first item in the array is also an array
1.65 +
1.66 + [["foo"]] 11 s s s 0 0 0
1.67 +
1.68 + However, to avoid overflow in the byte, we only do this 3 times. If the first
1.69 + item in an array is an array, and that array also has an array as first item,
1.70 + we simply write out the total value accumulated so far and then follow the
1.71 + "normal" rules.
1.72 +
1.73 + [[["foo"]]] 12 3 s s s 0 0 0 0
1.74 +
1.75 + There is another edge case that can happen though, which is that the array
1.76 + doesn't have a first item to which we can add 4 to the type. Instead the
1.77 + next byte would normally be the array terminator (per basic-strategy table)
1.78 + so we simply add the 4 there.
1.79 +
1.80 + [[]] 8 0 // 8 is 4 + 4 + 0
1.81 + [] 4 // 4 is 4 + 0
1.82 + [[], "foo"] 8 3 s s s 0 0 // 8 is 4 + 4 + 0
1.83 +
1.84 + Note that the max-3-times rule kicks in before we get a chance to add to the
1.85 + array terminator
1.86 +
1.87 + [[[]]] 12 0 0 0 // 12 is 4 + 4 + 4
1.88 +
1.89 + We could use a much higher number than 3 at no complexity or performance cost,
1.90 + however it seems unlikely that it'll make a practical difference, and the low
1.91 + limit makes testing eaiser.
1.92 +
1.93 +
1.94 + As a final optimization we do a post-encoding step which drops all 0s at the
1.95 + end of the encoded buffer.
1.96 +
1.97 + "foo" // 3 s s s
1.98 + 1 // 1 bf f0
1.99 + ["a", "b"] // 7 s 3 s
1.100 + [1, 2] // 5 bf f0 0 0 0 0 0 0 1 c0
1.101 + [[]] // 8
1.102 +*/
1.103 +
1.104 +const int MaxArrayCollapse = 3;
1.105 +
1.106 +const int MaxRecursionDepth = 256;
1.107 +
1.108 +nsresult
1.109 +Key::EncodeJSValInternal(JSContext* aCx, JS::Handle<JS::Value> aVal,
1.110 + uint8_t aTypeOffset, uint16_t aRecursionDepth)
1.111 +{
1.112 + NS_ENSURE_TRUE(aRecursionDepth < MaxRecursionDepth, NS_ERROR_DOM_INDEXEDDB_DATA_ERR);
1.113 +
1.114 + static_assert(eMaxType * MaxArrayCollapse < 256,
1.115 + "Unable to encode jsvals.");
1.116 +
1.117 + if (aVal.isString()) {
1.118 + nsDependentJSString str;
1.119 + if (!str.init(aCx, aVal)) {
1.120 + IDB_REPORT_INTERNAL_ERR();
1.121 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.122 + }
1.123 + EncodeString(str, aTypeOffset);
1.124 + return NS_OK;
1.125 + }
1.126 +
1.127 + if (aVal.isNumber()) {
1.128 + double d = aVal.toNumber();
1.129 + if (mozilla::IsNaN(d)) {
1.130 + return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
1.131 + }
1.132 + EncodeNumber(d, eFloat + aTypeOffset);
1.133 + return NS_OK;
1.134 + }
1.135 +
1.136 + if (aVal.isObject()) {
1.137 + JS::Rooted<JSObject*> obj(aCx, &aVal.toObject());
1.138 + if (JS_IsArrayObject(aCx, obj)) {
1.139 + aTypeOffset += eMaxType;
1.140 +
1.141 + if (aTypeOffset == eMaxType * MaxArrayCollapse) {
1.142 + mBuffer.Append(aTypeOffset);
1.143 + aTypeOffset = 0;
1.144 + }
1.145 + NS_ASSERTION((aTypeOffset % eMaxType) == 0 &&
1.146 + aTypeOffset < (eMaxType * MaxArrayCollapse),
1.147 + "Wrong typeoffset");
1.148 +
1.149 + uint32_t length;
1.150 + if (!JS_GetArrayLength(aCx, obj, &length)) {
1.151 + IDB_REPORT_INTERNAL_ERR();
1.152 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.153 + }
1.154 +
1.155 + for (uint32_t index = 0; index < length; index++) {
1.156 + JS::Rooted<JS::Value> val(aCx);
1.157 + if (!JS_GetElement(aCx, obj, index, &val)) {
1.158 + IDB_REPORT_INTERNAL_ERR();
1.159 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.160 + }
1.161 +
1.162 + nsresult rv = EncodeJSValInternal(aCx, val, aTypeOffset,
1.163 + aRecursionDepth + 1);
1.164 + if (NS_FAILED(rv)) {
1.165 + return rv;
1.166 + }
1.167 +
1.168 + aTypeOffset = 0;
1.169 + }
1.170 +
1.171 + mBuffer.Append(eTerminator + aTypeOffset);
1.172 +
1.173 + return NS_OK;
1.174 + }
1.175 +
1.176 + if (JS_ObjectIsDate(aCx, obj)) {
1.177 + if (!js_DateIsValid(obj)) {
1.178 + return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
1.179 + }
1.180 + EncodeNumber(js_DateGetMsecSinceEpoch(obj), eDate + aTypeOffset);
1.181 + return NS_OK;
1.182 + }
1.183 + }
1.184 +
1.185 + return NS_ERROR_DOM_INDEXEDDB_DATA_ERR;
1.186 +}
1.187 +
1.188 +// static
1.189 +nsresult
1.190 +Key::DecodeJSValInternal(const unsigned char*& aPos, const unsigned char* aEnd,
1.191 + JSContext* aCx, uint8_t aTypeOffset, JS::MutableHandle<JS::Value> aVal,
1.192 + uint16_t aRecursionDepth)
1.193 +{
1.194 + NS_ENSURE_TRUE(aRecursionDepth < MaxRecursionDepth, NS_ERROR_DOM_INDEXEDDB_DATA_ERR);
1.195 +
1.196 + if (*aPos - aTypeOffset >= eArray) {
1.197 + JS::Rooted<JSObject*> array(aCx, JS_NewArrayObject(aCx, 0));
1.198 + if (!array) {
1.199 + NS_WARNING("Failed to make array!");
1.200 + IDB_REPORT_INTERNAL_ERR();
1.201 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.202 + }
1.203 +
1.204 + aTypeOffset += eMaxType;
1.205 +
1.206 + if (aTypeOffset == eMaxType * MaxArrayCollapse) {
1.207 + ++aPos;
1.208 + aTypeOffset = 0;
1.209 + }
1.210 +
1.211 + uint32_t index = 0;
1.212 + JS::Rooted<JS::Value> val(aCx);
1.213 + while (aPos < aEnd && *aPos - aTypeOffset != eTerminator) {
1.214 + nsresult rv = DecodeJSValInternal(aPos, aEnd, aCx, aTypeOffset,
1.215 + &val, aRecursionDepth + 1);
1.216 + NS_ENSURE_SUCCESS(rv, rv);
1.217 +
1.218 + aTypeOffset = 0;
1.219 +
1.220 + if (!JS_SetElement(aCx, array, index++, val)) {
1.221 + NS_WARNING("Failed to set array element!");
1.222 + IDB_REPORT_INTERNAL_ERR();
1.223 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.224 + }
1.225 + }
1.226 +
1.227 + NS_ASSERTION(aPos >= aEnd || (*aPos % eMaxType) == eTerminator,
1.228 + "Should have found end-of-array marker");
1.229 + ++aPos;
1.230 +
1.231 + aVal.setObject(*array);
1.232 + }
1.233 + else if (*aPos - aTypeOffset == eString) {
1.234 + nsString key;
1.235 + DecodeString(aPos, aEnd, key);
1.236 + if (!xpc::StringToJsval(aCx, key, aVal)) {
1.237 + IDB_REPORT_INTERNAL_ERR();
1.238 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.239 + }
1.240 + }
1.241 + else if (*aPos - aTypeOffset == eDate) {
1.242 + double msec = static_cast<double>(DecodeNumber(aPos, aEnd));
1.243 + JSObject* date = JS_NewDateObjectMsec(aCx, msec);
1.244 + if (!date) {
1.245 + IDB_WARNING("Failed to make date!");
1.246 + return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
1.247 + }
1.248 +
1.249 + aVal.setObject(*date);
1.250 + }
1.251 + else if (*aPos - aTypeOffset == eFloat) {
1.252 + aVal.setDouble(DecodeNumber(aPos, aEnd));
1.253 + }
1.254 + else {
1.255 + NS_NOTREACHED("Unknown key type!");
1.256 + }
1.257 +
1.258 + return NS_OK;
1.259 +}
1.260 +
1.261 +#define ONE_BYTE_LIMIT 0x7E
1.262 +#define TWO_BYTE_LIMIT (0x3FFF+0x7F)
1.263 +
1.264 +#define ONE_BYTE_ADJUST 1
1.265 +#define TWO_BYTE_ADJUST (-0x7F)
1.266 +#define THREE_BYTE_SHIFT 6
1.267 +
1.268 +void
1.269 +Key::EncodeString(const nsAString& aString, uint8_t aTypeOffset)
1.270 +{
1.271 + // First measure how long the encoded string will be.
1.272 +
1.273 + // The +2 is for initial 3 and trailing 0. We'll compensate for multi-byte
1.274 + // chars below.
1.275 + uint32_t size = aString.Length() + 2;
1.276 +
1.277 + const char16_t* start = aString.BeginReading();
1.278 + const char16_t* end = aString.EndReading();
1.279 + for (const char16_t* iter = start; iter < end; ++iter) {
1.280 + if (*iter > ONE_BYTE_LIMIT) {
1.281 + size += *iter > TWO_BYTE_LIMIT ? 2 : 1;
1.282 + }
1.283 + }
1.284 +
1.285 + // Allocate memory for the new size
1.286 + uint32_t oldLen = mBuffer.Length();
1.287 + char* buffer;
1.288 + if (!mBuffer.GetMutableData(&buffer, oldLen + size)) {
1.289 + return;
1.290 + }
1.291 + buffer += oldLen;
1.292 +
1.293 + // Write type marker
1.294 + *(buffer++) = eString + aTypeOffset;
1.295 +
1.296 + // Encode string
1.297 + for (const char16_t* iter = start; iter < end; ++iter) {
1.298 + if (*iter <= ONE_BYTE_LIMIT) {
1.299 + *(buffer++) = *iter + ONE_BYTE_ADJUST;
1.300 + }
1.301 + else if (*iter <= TWO_BYTE_LIMIT) {
1.302 + char16_t c = char16_t(*iter) + TWO_BYTE_ADJUST + 0x8000;
1.303 + *(buffer++) = (char)(c >> 8);
1.304 + *(buffer++) = (char)(c & 0xFF);
1.305 + }
1.306 + else {
1.307 + uint32_t c = (uint32_t(*iter) << THREE_BYTE_SHIFT) | 0x00C00000;
1.308 + *(buffer++) = (char)(c >> 16);
1.309 + *(buffer++) = (char)(c >> 8);
1.310 + *(buffer++) = (char)c;
1.311 + }
1.312 + }
1.313 +
1.314 + // Write end marker
1.315 + *(buffer++) = eTerminator;
1.316 +
1.317 + NS_ASSERTION(buffer == mBuffer.EndReading(), "Wrote wrong number of bytes");
1.318 +}
1.319 +
1.320 +// static
1.321 +void
1.322 +Key::DecodeString(const unsigned char*& aPos, const unsigned char* aEnd,
1.323 + nsString& aString)
1.324 +{
1.325 + NS_ASSERTION(*aPos % eMaxType == eString, "Don't call me!");
1.326 +
1.327 + const unsigned char* buffer = aPos + 1;
1.328 +
1.329 + // First measure how big the decoded string will be.
1.330 + uint32_t size = 0;
1.331 + const unsigned char* iter;
1.332 + for (iter = buffer; iter < aEnd && *iter != eTerminator; ++iter) {
1.333 + if (*iter & 0x80) {
1.334 + iter += (*iter & 0x40) ? 2 : 1;
1.335 + }
1.336 + ++size;
1.337 + }
1.338 +
1.339 + // Set end so that we don't have to check for null termination in the loop
1.340 + // below
1.341 + if (iter < aEnd) {
1.342 + aEnd = iter;
1.343 + }
1.344 +
1.345 + char16_t* out;
1.346 + if (size && !aString.GetMutableData(&out, size)) {
1.347 + return;
1.348 + }
1.349 +
1.350 + for (iter = buffer; iter < aEnd;) {
1.351 + if (!(*iter & 0x80)) {
1.352 + *out = *(iter++) - ONE_BYTE_ADJUST;
1.353 + }
1.354 + else if (!(*iter & 0x40)) {
1.355 + char16_t c = (char16_t(*(iter++)) << 8);
1.356 + if (iter < aEnd) {
1.357 + c |= *(iter++);
1.358 + }
1.359 + *out = c - TWO_BYTE_ADJUST - 0x8000;
1.360 + }
1.361 + else {
1.362 + uint32_t c = uint32_t(*(iter++)) << (16 - THREE_BYTE_SHIFT);
1.363 + if (iter < aEnd) {
1.364 + c |= uint32_t(*(iter++)) << (8 - THREE_BYTE_SHIFT);
1.365 + }
1.366 + if (iter < aEnd) {
1.367 + c |= *(iter++) >> THREE_BYTE_SHIFT;
1.368 + }
1.369 + *out = (char16_t)c;
1.370 + }
1.371 +
1.372 + ++out;
1.373 + }
1.374 +
1.375 + NS_ASSERTION(!size || out == aString.EndReading(),
1.376 + "Should have written the whole string");
1.377 +
1.378 + aPos = iter + 1;
1.379 +}
1.380 +
1.381 +union Float64Union {
1.382 + double d;
1.383 + uint64_t u;
1.384 +};
1.385 +
1.386 +void
1.387 +Key::EncodeNumber(double aFloat, uint8_t aType)
1.388 +{
1.389 + // Allocate memory for the new size
1.390 + uint32_t oldLen = mBuffer.Length();
1.391 + char* buffer;
1.392 + if (!mBuffer.GetMutableData(&buffer, oldLen + 1 + sizeof(double))) {
1.393 + return;
1.394 + }
1.395 + buffer += oldLen;
1.396 +
1.397 + *(buffer++) = aType;
1.398 +
1.399 + Float64Union pun;
1.400 + pun.d = aFloat;
1.401 + // Note: The subtraction from 0 below is necessary to fix
1.402 + // MSVC build warning C4146 (negating an unsigned value).
1.403 + uint64_t number = pun.u & PR_UINT64(0x8000000000000000) ?
1.404 + (0 - pun.u) :
1.405 + (pun.u | PR_UINT64(0x8000000000000000));
1.406 +
1.407 + mozilla::BigEndian::writeUint64(buffer, number);
1.408 +}
1.409 +
1.410 +// static
1.411 +double
1.412 +Key::DecodeNumber(const unsigned char*& aPos, const unsigned char* aEnd)
1.413 +{
1.414 + NS_ASSERTION(*aPos % eMaxType == eFloat ||
1.415 + *aPos % eMaxType == eDate, "Don't call me!");
1.416 +
1.417 + ++aPos;
1.418 +
1.419 + uint64_t number = 0;
1.420 + memcpy(&number, aPos, std::min<size_t>(sizeof(number), aEnd - aPos));
1.421 + number = mozilla::NativeEndian::swapFromBigEndian(number);
1.422 +
1.423 + aPos += sizeof(number);
1.424 +
1.425 + Float64Union pun;
1.426 + // Note: The subtraction from 0 below is necessary to fix
1.427 + // MSVC build warning C4146 (negating an unsigned value).
1.428 + pun.u = number & PR_UINT64(0x8000000000000000) ?
1.429 + (number & ~PR_UINT64(0x8000000000000000)) :
1.430 + (0 - number);
1.431 +
1.432 + return pun.d;
1.433 +}
