From f5db1b5f6a04d5f08671ae4cee2eea8283a578aa Mon Sep 17 00:00:00 2001 From: Peter Varga Date: Fri, 28 Sep 2012 14:06:56 +0200 Subject: Add testcase for Strign::ComputeHash function The qcalculatehash_p.h private header also has been added to provide function calculatehash for qml and the new testcase. Change-Id: I1a0cf6052f596438f50bb5d2899ceaaae3e2e477 Reviewed-by: Simon Hausmann --- src/v8/qcalculatehash_p.h | 140 ++++++++++++++++++++++++++++++++++++++++++++++ sync.profile | 2 +- tests/auto/v8/tst_v8.cpp | 6 ++ tests/auto/v8/v8main.cpp | 1 + tests/auto/v8/v8test.cpp | 54 ++++++++++++++++++ tests/auto/v8/v8test.h | 1 + 6 files changed, 203 insertions(+), 1 deletion(-) create mode 100644 src/v8/qcalculatehash_p.h diff --git a/src/v8/qcalculatehash_p.h b/src/v8/qcalculatehash_p.h new file mode 100644 index 0000000..715fa6e --- /dev/null +++ b/src/v8/qcalculatehash_p.h @@ -0,0 +1,140 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the QtV8 module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef CALCULATEHASH_P_H +#define CALCULATEHASH_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include +#include + +QT_BEGIN_NAMESPACE + +// This is a reimplementation of V8's string hash algorithm. It is significantly +// faster to do it here than call into V8, but it adds the maintenance burden of +// ensuring that the two hashes are identical. We Q_ASSERT() that the two return +// the same value. If these asserts start to fail, the hash code needs to be +// synced with V8. +namespace HashedString { + static const int kMaxArrayIndexSize = 10; + static const int kMaxHashCalcLength = 16383; + static const int kNofHashBitFields = 2; + static const int kHashShift = kNofHashBitFields; + static const int kIsNotArrayIndexMask = 1 << 1; + static const int kArrayIndexValueBits = 24; + static const int kArrayIndexHashLengthShift = kArrayIndexValueBits + kNofHashBitFields; + static const int kMaxCachedArrayIndexLength = 7; +}; + +template +uint32_t calculateHash(const schar* chars, int length) { + if (length > HashedString::kMaxHashCalcLength) { + // V8 trivial hash + return (length << HashedString::kHashShift) | HashedString::kIsNotArrayIndexMask; + } + + uint32_t raw_running_hash = 0; + uint32_t array_index = 0; + bool is_array_index = (0 < length && length <= HashedString::kMaxArrayIndexSize); + bool is_first_char = true; + + int ii = 0; + for (;is_array_index && ii < length; ++ii) { + quint32 c = *chars++; + + raw_running_hash += c; + raw_running_hash += (raw_running_hash << 10); + raw_running_hash ^= (raw_running_hash >> 6); + + if (c < '0' || c > '9') { + is_array_index = false; + } else { + int d = c - '0'; + if (is_first_char) { + is_first_char = false; + if (c == '0' && length > 1) { + is_array_index = false; + continue; + } + } + if (array_index > 429496729U - ((d + 2) >> 3)) { + is_array_index = false; + } else { + array_index = array_index * 10 + d; + } + } + } + + for (;ii < length; ++ii) { + raw_running_hash += *chars++; + raw_running_hash += (raw_running_hash << 10); + raw_running_hash ^= (raw_running_hash >> 6); + } + + if (is_array_index) { + array_index <<= HashedString::kHashShift; + array_index |= length << HashedString::kArrayIndexHashLengthShift; + return array_index; + } else { + raw_running_hash += (raw_running_hash << 3); + raw_running_hash ^= (raw_running_hash >> 11); + raw_running_hash += (raw_running_hash << 15); + if (raw_running_hash == 0) { + raw_running_hash = 27; + } + + return (raw_running_hash << HashedString::kHashShift) | HashedString::kIsNotArrayIndexMask; + } +} + +QT_END_NAMESPACE + +#endif // CALCULATEHASH_P_H diff --git a/sync.profile b/sync.profile index 05b86d2..ed2a91a 100644 --- a/sync.profile +++ b/sync.profile @@ -2,7 +2,7 @@ "QtV8" => "$basedir/src/v8", ); %moduleheaders = ( # restrict the module headers to those found in relative path - "QtV8" => "../3rdparty/v8/include", + "QtV8" => "../3rdparty/v8/include;../v8", ); @allmoduleheadersprivate = ( "QtV8" diff --git a/tests/auto/v8/tst_v8.cpp b/tests/auto/v8/tst_v8.cpp index b8ad5d5..235158e 100644 --- a/tests/auto/v8/tst_v8.cpp +++ b/tests/auto/v8/tst_v8.cpp @@ -67,6 +67,7 @@ private slots: void fallbackpropertyhandler_in_prototype(); void fallbackpropertyhandler_nonempty(); void completehash(); + void stringhashcomparison(); }; void tst_v8::eval() @@ -134,6 +135,11 @@ void tst_v8::completehash() QVERIFY(v8test_completehash()); } +void tst_v8::stringhashcomparison() +{ + QVERIFY(v8test_stringhashcomparison()); +} + int main(int argc, char *argv[]) { V8::SetFlagsFromCommandLine(&argc, argv, true); diff --git a/tests/auto/v8/v8main.cpp b/tests/auto/v8/v8main.cpp index c2b3de2..ebb5b24 100644 --- a/tests/auto/v8/v8main.cpp +++ b/tests/auto/v8/v8main.cpp @@ -72,6 +72,7 @@ int main(int argc, char *argv[]) RUN_TEST(fallbackpropertyhandler_callbacks); RUN_TEST(fallbackpropertyhandler_in_prototype); RUN_TEST(fallbackpropertyhandler_nonempty); + RUN_TEST(stringhashcomparison); return exit_status; } diff --git a/tests/auto/v8/v8test.cpp b/tests/auto/v8/v8test.cpp index 09410a6..2145acb 100644 --- a/tests/auto/v8/v8test.cpp +++ b/tests/auto/v8/v8test.cpp @@ -40,6 +40,7 @@ ****************************************************************************/ #include "v8test.h" +#include using namespace v8; @@ -1089,3 +1090,56 @@ cleanup: ENDTEST(); } + +bool v8test_stringhashcomparison() +{ + BEGINTEST(); + + // Initialize V8 random seed for string hashing + HandleScope handle_scope; + Persistent context = Context::New(); + Context::Scope context_scope(context); + + quint32 hash1; + uint32_t hash2; + int length, rand; + + const char* text; + QString qtext; + + char textRand[HashedString::kMaxHashCalcLength + 1]; + QString qtextRand; + + text = "tipli"; + qtext = QString(text); + length = strlen(text); + + hash1 = calculateHash((uint8_t*)text, length) >> HashedString::kHashShift; + hash2 = String::ComputeHash((char*)text, length); + VERIFY(hash1 == hash2); + + hash1 = calculateHash((quint16*)qtext.constData(), length) >> HashedString::kHashShift; + hash2 = String::ComputeHash((uint16_t*)qtext.constData(), length); + VERIFY(hash1 == hash2); + + // Check V8 trivial hash + length = HashedString::kMaxHashCalcLength + 1; + for (int i = 0; i < length; i++) { + rand = qrand() % 255 + 1; + textRand[i] = (char)rand; + } + qtextRand = QString(textRand); + + hash1 = calculateHash((uint8_t*)textRand, length) >> HashedString::kHashShift; + hash2 = String::ComputeHash((char*)textRand, length); + VERIFY(hash1 == hash2); + + hash1 = calculateHash((quint16*)qtextRand.constData(), length) >> HashedString::kHashShift; + hash2 = String::ComputeHash((uint16_t*)qtextRand.constData(), length); + VERIFY(hash1 == hash2); + +cleanup: + context.Dispose(); + + ENDTEST(); +} diff --git a/tests/auto/v8/v8test.h b/tests/auto/v8/v8test.h index c195b67..4132fd4 100644 --- a/tests/auto/v8/v8test.h +++ b/tests/auto/v8/v8test.h @@ -61,6 +61,7 @@ bool v8test_fallbackpropertyhandler_callbacks(); bool v8test_fallbackpropertyhandler_in_prototype(); bool v8test_fallbackpropertyhandler_nonempty(); bool v8test_completehash(); +bool v8test_stringhashcomparison(); #endif // V8TEST_H -- cgit v1.2.3