From 410b4b2db48854bcd6561919a4d97a02c9564630 Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Wed, 17 Jul 2013 11:37:20 +0000 Subject: [PATCH] Reland "Turn ElementsTransitionAndStore stub into a HydrogenCodeStub". Fix the invalid array length check, replacing it with a check of the elements pointer similar to TransitionElementsKindStub. Refactor common code from ElementsTransitionAndStoreStub and TransitionElementsKindStub into BuildTransitionElementsKind() helper method. Add test case for the MD5 computation that used to crash before, and a small test case for the specific issue. R=danno@chromium.org Review URL: https://codereview.chromium.org/19367003 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15713 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/code-stubs-arm.cc | 11 ++ src/code-stubs-hydrogen.cc | 76 +++++----- src/code-stubs.cc | 2 +- src/code-stubs.h | 56 ++++++- src/hydrogen.cc | 42 +++++ src/hydrogen.h | 6 + src/ia32/code-stubs-ia32.cc | 11 ++ src/ic.cc | 18 +++ src/ic.h | 1 + src/mips/code-stubs-mips.cc | 11 ++ src/stub-cache.cc | 21 ++- src/x64/code-stubs-x64.cc | 11 ++ test/mjsunit/elements-transition-and-store.js | 41 +++++ test/mjsunit/md5.js | 211 ++++++++++++++++++++++++++ 14 files changed, 471 insertions(+), 47 deletions(-) create mode 100644 test/mjsunit/elements-transition-and-store.js create mode 100644 test/mjsunit/md5.js diff --git a/src/arm/code-stubs-arm.cc b/src/arm/code-stubs-arm.cc index ff754ec..8f8094f 100644 --- a/src/arm/code-stubs-arm.cc +++ b/src/arm/code-stubs-arm.cc @@ -258,6 +258,17 @@ void StoreGlobalStub::InitializeInterfaceDescriptor( } +void ElementsTransitionAndStoreStub::InitializeInterfaceDescriptor( + Isolate* isolate, + CodeStubInterfaceDescriptor* descriptor) { + static Register registers[] = { r0, r3, r1, r2 }; + descriptor->register_param_count_ = 4; + descriptor->register_params_ = registers; + descriptor->deoptimization_handler_ = + FUNCTION_ADDR(ElementsTransitionAndStoreIC_Miss); +} + + #define __ ACCESS_MASM(masm) diff --git a/src/code-stubs-hydrogen.cc b/src/code-stubs-hydrogen.cc index 9ea87ab..25715cb 100644 --- a/src/code-stubs-hydrogen.cc +++ b/src/code-stubs-hydrogen.cc @@ -528,44 +528,15 @@ Handle KeyedStoreFastElementStub::GenerateCode() { template <> HValue* CodeStubGraphBuilder::BuildCodeStub() { - TransitionElementsKindStub* stub = casted_stub(); - ElementsKind from_kind = stub->from_kind(); - ElementsKind to_kind = stub->to_kind(); - - HValue* js_array = GetParameter(0); - HValue* map = GetParameter(1); - info()->MarkAsSavesCallerDoubles(); - if (AllocationSite::GetMode(from_kind, to_kind) == TRACK_ALLOCATION_SITE) { - Add(js_array); - } - - HInstruction* elements = AddLoadElements(js_array); - - HInstruction* empty_fixed_array = Add( - isolate()->factory()->empty_fixed_array(), Representation::Tagged()); - - IfBuilder if_builder(this); - - if_builder.IfNot(elements, empty_fixed_array); - - if_builder.Then(); - - HInstruction* elements_length = AddLoadFixedArrayLength(elements); - - HInstruction* array_length = AddLoad( - js_array, HObjectAccess::ForArrayLength(), NULL, Representation::Smi()); - array_length->set_type(HType::Smi()); - - BuildGrowElementsCapacity(js_array, elements, from_kind, to_kind, - array_length, elements_length); - - if_builder.End(); - - AddStore(js_array, HObjectAccess::ForMap(), map); + BuildTransitionElementsKind(GetParameter(0), + GetParameter(1), + casted_stub()->from_kind(), + casted_stub()->to_kind(), + true); - return js_array; + return GetParameter(0); } @@ -910,4 +881,39 @@ Handle StoreGlobalStub::GenerateCode() { } +template<> +HValue* CodeStubGraphBuilder::BuildCodeStub() { + HValue* value = GetParameter(0); + HValue* map = GetParameter(1); + HValue* key = GetParameter(2); + HValue* object = GetParameter(3); + + if (FLAG_trace_elements_transitions) { + // Tracing elements transitions is the job of the runtime. + current_block()->FinishExitWithDeoptimization(HDeoptimize::kUseAll); + set_current_block(NULL); + } else { + info()->MarkAsSavesCallerDoubles(); + + BuildTransitionElementsKind(object, map, + casted_stub()->from_kind(), + casted_stub()->to_kind(), + casted_stub()->is_jsarray()); + + BuildUncheckedMonomorphicElementAccess(object, key, value, NULL, + casted_stub()->is_jsarray(), + casted_stub()->to_kind(), + true, ALLOW_RETURN_HOLE, + casted_stub()->store_mode()); + } + + return value; +} + + +Handle ElementsTransitionAndStoreStub::GenerateCode() { + return DoGenerateCode(this); +} + + } } // namespace v8::internal diff --git a/src/code-stubs.cc b/src/code-stubs.cc index 7e7125d..9d40ad0 100644 --- a/src/code-stubs.cc +++ b/src/code-stubs.cc @@ -818,7 +818,7 @@ bool ToBooleanStub::Types::CanBeUndetectable() const { } -void ElementsTransitionAndStoreStub::Generate(MacroAssembler* masm) { +void ElementsTransitionAndStorePlatformStub::Generate(MacroAssembler* masm) { Label fail; AllocationSiteMode mode = AllocationSite::GetMode(from_, to_); ASSERT(!IsFastHoleyElementsKind(from_) || IsFastHoleyElementsKind(to_)); diff --git a/src/code-stubs.h b/src/code-stubs.h index 17f9200..131887d 100644 --- a/src/code-stubs.h +++ b/src/code-stubs.h @@ -2245,13 +2245,59 @@ class ToBooleanStub: public HydrogenCodeStub { }; -class ElementsTransitionAndStoreStub : public PlatformCodeStub { +class ElementsTransitionAndStoreStub : public HydrogenCodeStub { public: - ElementsTransitionAndStoreStub(ElementsKind from, - ElementsKind to, + ElementsTransitionAndStoreStub(ElementsKind from_kind, + ElementsKind to_kind, bool is_jsarray, - StrictModeFlag strict_mode, KeyedAccessStoreMode store_mode) + : from_kind_(from_kind), + to_kind_(to_kind), + is_jsarray_(is_jsarray), + store_mode_(store_mode) {} + + ElementsKind from_kind() const { return from_kind_; } + ElementsKind to_kind() const { return to_kind_; } + bool is_jsarray() const { return is_jsarray_; } + KeyedAccessStoreMode store_mode() const { return store_mode_; } + + Handle GenerateCode(); + + void InitializeInterfaceDescriptor( + Isolate* isolate, + CodeStubInterfaceDescriptor* descriptor); + + private: + class FromBits: public BitField {}; + class ToBits: public BitField {}; + class IsJSArrayBits: public BitField {}; + class StoreModeBits: public BitField {}; + + Major MajorKey() { return ElementsTransitionAndStore; } + int NotMissMinorKey() { + return FromBits::encode(from_kind_) | + ToBits::encode(to_kind_) | + IsJSArrayBits::encode(is_jsarray_) | + StoreModeBits::encode(store_mode_); + } + + ElementsKind from_kind_; + ElementsKind to_kind_; + bool is_jsarray_; + KeyedAccessStoreMode store_mode_; + + DISALLOW_COPY_AND_ASSIGN(ElementsTransitionAndStoreStub); +}; + + +// TODO(bmeurer) Remove this when compiled transitions is enabled +class ElementsTransitionAndStorePlatformStub : public PlatformCodeStub { + public: + ElementsTransitionAndStorePlatformStub(ElementsKind from, + ElementsKind to, + bool is_jsarray, + StrictModeFlag strict_mode, + KeyedAccessStoreMode store_mode) : from_(from), to_(to), is_jsarray_(is_jsarray), @@ -2282,7 +2328,7 @@ class ElementsTransitionAndStoreStub : public PlatformCodeStub { StrictModeFlag strict_mode_; KeyedAccessStoreMode store_mode_; - DISALLOW_COPY_AND_ASSIGN(ElementsTransitionAndStoreStub); + DISALLOW_COPY_AND_ASSIGN(ElementsTransitionAndStorePlatformStub); }; diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 409a0d4..c1e7490 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -1223,6 +1223,48 @@ HValue* HGraphBuilder::BuildCopyElementsOnWrite(HValue* object, } +void HGraphBuilder::BuildTransitionElementsKind(HValue* object, + HValue* map, + ElementsKind from_kind, + ElementsKind to_kind, + bool is_jsarray) { + ASSERT(!IsFastHoleyElementsKind(from_kind) || + IsFastHoleyElementsKind(to_kind)); + + if (AllocationSite::GetMode(from_kind, to_kind) == TRACK_ALLOCATION_SITE) { + Add(object); + } + + if (!IsSimpleMapChangeTransition(from_kind, to_kind)) { + HInstruction* elements = AddLoadElements(object); + + HInstruction* empty_fixed_array = Add( + isolate()->factory()->empty_fixed_array(), Representation::Tagged()); + + IfBuilder if_builder(this); + + if_builder.IfNot(elements, empty_fixed_array); + + if_builder.Then(); + + HInstruction* elements_length = AddLoadFixedArrayLength(elements); + + HInstruction* array_length = is_jsarray + ? AddLoad(object, HObjectAccess::ForArrayLength(), + NULL, Representation::Smi()) + : elements_length; + array_length->set_type(HType::Smi()); + + BuildGrowElementsCapacity(object, elements, from_kind, to_kind, + array_length, elements_length); + + if_builder.End(); + } + + AddStore(object, HObjectAccess::ForMap(), map); +} + + HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess( HValue* object, HValue* key, diff --git a/src/hydrogen.h b/src/hydrogen.h index 09700ef..4c80280 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -1076,6 +1076,12 @@ class HGraphBuilder { ElementsKind kind, HValue* length); + void BuildTransitionElementsKind(HValue* object, + HValue* map, + ElementsKind from_kind, + ElementsKind to_kind, + bool is_jsarray); + HInstruction* BuildUncheckedMonomorphicElementAccess( HValue* object, HValue* key, diff --git a/src/ia32/code-stubs-ia32.cc b/src/ia32/code-stubs-ia32.cc index 7cf9b44..aee57dc 100644 --- a/src/ia32/code-stubs-ia32.cc +++ b/src/ia32/code-stubs-ia32.cc @@ -262,6 +262,17 @@ void StoreGlobalStub::InitializeInterfaceDescriptor( } +void ElementsTransitionAndStoreStub::InitializeInterfaceDescriptor( + Isolate* isolate, + CodeStubInterfaceDescriptor* descriptor) { + static Register registers[] = { eax, ebx, ecx, edx }; + descriptor->register_param_count_ = 4; + descriptor->register_params_ = registers; + descriptor->deoptimization_handler_ = + FUNCTION_ADDR(ElementsTransitionAndStoreIC_Miss); +} + + #define __ ACCESS_MASM(masm) diff --git a/src/ic.cc b/src/ic.cc index e09d83e..e085245 100644 --- a/src/ic.cc +++ b/src/ic.cc @@ -2481,6 +2481,24 @@ RUNTIME_FUNCTION(MaybeObject*, KeyedStoreIC_MissForceGeneric) { } +RUNTIME_FUNCTION(MaybeObject*, ElementsTransitionAndStoreIC_Miss) { + SealHandleScope scope(isolate); + ASSERT(args.length() == 4); + KeyedStoreIC ic(IC::EXTRA_CALL_FRAME, isolate); + Code::ExtraICState extra_ic_state = ic.target()->extra_ic_state(); + Handle value = args.at(0); + Handle key = args.at(2); + Handle object = args.at(3); + StrictModeFlag strict_mode = Code::GetStrictMode(extra_ic_state); + return Runtime::SetObjectProperty(isolate, + object, + key, + value, + NONE, + strict_mode); +} + + void BinaryOpIC::patch(Code* code) { set_target(code); } diff --git a/src/ic.h b/src/ic.h index aa867cc..c9f521f 100644 --- a/src/ic.h +++ b/src/ic.h @@ -858,6 +858,7 @@ DECLARE_RUNTIME_FUNCTION(MaybeObject*, KeyedLoadIC_MissFromStubFailure); DECLARE_RUNTIME_FUNCTION(MaybeObject*, KeyedStoreIC_MissFromStubFailure); DECLARE_RUNTIME_FUNCTION(MaybeObject*, UnaryOpIC_Miss); DECLARE_RUNTIME_FUNCTION(MaybeObject*, StoreIC_MissFromStubFailure); +DECLARE_RUNTIME_FUNCTION(MaybeObject*, ElementsTransitionAndStoreIC_Miss); DECLARE_RUNTIME_FUNCTION(MaybeObject*, CompareNilIC_Miss); DECLARE_RUNTIME_FUNCTION(MaybeObject*, ToBooleanIC_Miss); diff --git a/src/mips/code-stubs-mips.cc b/src/mips/code-stubs-mips.cc index 29178eb..c4a4bdc 100644 --- a/src/mips/code-stubs-mips.cc +++ b/src/mips/code-stubs-mips.cc @@ -259,6 +259,17 @@ void StoreGlobalStub::InitializeInterfaceDescriptor( } +void ElementsTransitionAndStoreStub::InitializeInterfaceDescriptor( + Isolate* isolate, + CodeStubInterfaceDescriptor* descriptor) { + static Register registers[] = { a0, a3, a1, a2 }; + descriptor->register_param_count_ = 4; + descriptor->register_params_ = registers; + descriptor->deoptimization_handler_ = + FUNCTION_ADDR(ElementsTransitionAndStoreIC_Miss); +} + + #define __ ACCESS_MASM(masm) diff --git a/src/stub-cache.cc b/src/stub-cache.cc index dec7a9d..436cd46 100644 --- a/src/stub-cache.cc +++ b/src/stub-cache.cc @@ -1993,12 +1993,21 @@ Handle KeyedStoreStubCompiler::CompileStoreElementPolymorphic( bool is_js_array = receiver_map->instance_type() == JS_ARRAY_TYPE; ElementsKind elements_kind = receiver_map->elements_kind(); if (!transitioned_map.is_null()) { - cached_stub = ElementsTransitionAndStoreStub( - elements_kind, - transitioned_map->elements_kind(), - is_js_array, - strict_mode(), - store_mode_).GetCode(isolate()); + if (FLAG_compiled_transitions) { + cached_stub = ElementsTransitionAndStoreStub( + elements_kind, + transitioned_map->elements_kind(), + is_js_array, + store_mode_).GetCode(isolate()); + } else { + // TODO(bmeurer) Remove this when compiled transitions is enabled + cached_stub = ElementsTransitionAndStorePlatformStub( + elements_kind, + transitioned_map->elements_kind(), + is_js_array, + strict_mode(), + store_mode_).GetCode(isolate()); + } } else { if (FLAG_compiled_keyed_stores && (receiver_map->has_fast_elements() || diff --git a/src/x64/code-stubs-x64.cc b/src/x64/code-stubs-x64.cc index 0c0c272..0b74ace 100644 --- a/src/x64/code-stubs-x64.cc +++ b/src/x64/code-stubs-x64.cc @@ -258,6 +258,17 @@ void StoreGlobalStub::InitializeInterfaceDescriptor( } +void ElementsTransitionAndStoreStub::InitializeInterfaceDescriptor( + Isolate* isolate, + CodeStubInterfaceDescriptor* descriptor) { + static Register registers[] = { rax, rbx, rcx, rdx }; + descriptor->register_param_count_ = 4; + descriptor->register_params_ = registers; + descriptor->deoptimization_handler_ = + FUNCTION_ADDR(ElementsTransitionAndStoreIC_Miss); +} + + #define __ ACCESS_MASM(masm) diff --git a/test/mjsunit/elements-transition-and-store.js b/test/mjsunit/elements-transition-and-store.js new file mode 100644 index 0000000..78ca597 --- /dev/null +++ b/test/mjsunit/elements-transition-and-store.js @@ -0,0 +1,41 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// Flags: --compiled-transitions --notrack-allocation-sites + +function foo(a, v) { + a[0] = v; + return a; +} + +for (var i = 0; i < 3; ++i) { + var a = Array(); + a = foo(a, 1.5); + assertEquals(a[0], 1.5); + a = foo(a, 2); + assertEquals(a[0], 2); +} diff --git a/test/mjsunit/md5.js b/test/mjsunit/md5.js new file mode 100644 index 0000000..38dc802 --- /dev/null +++ b/test/mjsunit/md5.js @@ -0,0 +1,211 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// A JavaScript implementation of the RSA Data Security, Inc. MD5 Message +// Digest Algorithm, as defined in RFC 1321. +// Version 2.1 Copyright (C) Paul Johnston 1999 - 2002. +// Other contributors: Greg Holt, Andrew Kepert, Ydnar, Lostinet +// Distributed under the BSD License +// See http://pajhome.org.uk/crypt/md5 for more info. +// + +function hex_md5(s) { + return binl2hex(core_md5(str2binl(s), s.length * 8)); +} + +function core_md5(x, len) { + /* append padding */ + x[len >> 5] |= 0x80 << ((len) % 32); + x[(((len + 64) >>> 9) << 4) + 14] = len; + + var a = 1732584193; + var b = -271733879; + var c = -1732584194; + var d = 271733878; + + for (var i = 0; i < x.length; i += 16) { + var olda = a; + var oldb = b; + var oldc = c; + var oldd = d; + + a = md5_ff(a, b, c, d, x[i+ 0], 7 , -680876936); + d = md5_ff(d, a, b, c, x[i+ 1], 12, -389564586); + c = md5_ff(c, d, a, b, x[i+ 2], 17, 606105819); + b = md5_ff(b, c, d, a, x[i+ 3], 22, -1044525330); + a = md5_ff(a, b, c, d, x[i+ 4], 7 , -176418897); + d = md5_ff(d, a, b, c, x[i+ 5], 12, 1200080426); + c = md5_ff(c, d, a, b, x[i+ 6], 17, -1473231341); + b = md5_ff(b, c, d, a, x[i+ 7], 22, -45705983); + a = md5_ff(a, b, c, d, x[i+ 8], 7 , 1770035416); + d = md5_ff(d, a, b, c, x[i+ 9], 12, -1958414417); + c = md5_ff(c, d, a, b, x[i+10], 17, -42063); + b = md5_ff(b, c, d, a, x[i+11], 22, -1990404162); + a = md5_ff(a, b, c, d, x[i+12], 7 , 1804603682); + d = md5_ff(d, a, b, c, x[i+13], 12, -40341101); + c = md5_ff(c, d, a, b, x[i+14], 17, -1502002290); + b = md5_ff(b, c, d, a, x[i+15], 22, 1236535329); + + a = md5_gg(a, b, c, d, x[i+ 1], 5 , -165796510); + d = md5_gg(d, a, b, c, x[i+ 6], 9 , -1069501632); + c = md5_gg(c, d, a, b, x[i+11], 14, 643717713); + b = md5_gg(b, c, d, a, x[i+ 0], 20, -373897302); + a = md5_gg(a, b, c, d, x[i+ 5], 5 , -701558691); + d = md5_gg(d, a, b, c, x[i+10], 9 , 38016083); + c = md5_gg(c, d, a, b, x[i+15], 14, -660478335); + b = md5_gg(b, c, d, a, x[i+ 4], 20, -405537848); + a = md5_gg(a, b, c, d, x[i+ 9], 5 , 568446438); + d = md5_gg(d, a, b, c, x[i+14], 9 , -1019803690); + c = md5_gg(c, d, a, b, x[i+ 3], 14, -187363961); + b = md5_gg(b, c, d, a, x[i+ 8], 20, 1163531501); + a = md5_gg(a, b, c, d, x[i+13], 5 , -1444681467); + d = md5_gg(d, a, b, c, x[i+ 2], 9 , -51403784); + c = md5_gg(c, d, a, b, x[i+ 7], 14, 1735328473); + b = md5_gg(b, c, d, a, x[i+12], 20, -1926607734); + + a = md5_hh(a, b, c, d, x[i+ 5], 4 , -378558); + d = md5_hh(d, a, b, c, x[i+ 8], 11, -2022574463); + c = md5_hh(c, d, a, b, x[i+11], 16, 1839030562); + b = md5_hh(b, c, d, a, x[i+14], 23, -35309556); + a = md5_hh(a, b, c, d, x[i+ 1], 4 , -1530992060); + d = md5_hh(d, a, b, c, x[i+ 4], 11, 1272893353); + c = md5_hh(c, d, a, b, x[i+ 7], 16, -155497632); + b = md5_hh(b, c, d, a, x[i+10], 23, -1094730640); + a = md5_hh(a, b, c, d, x[i+13], 4 , 681279174); + d = md5_hh(d, a, b, c, x[i+ 0], 11, -358537222); + c = md5_hh(c, d, a, b, x[i+ 3], 16, -722521979); + b = md5_hh(b, c, d, a, x[i+ 6], 23, 76029189); + a = md5_hh(a, b, c, d, x[i+ 9], 4 , -640364487); + d = md5_hh(d, a, b, c, x[i+12], 11, -421815835); + c = md5_hh(c, d, a, b, x[i+15], 16, 530742520); + b = md5_hh(b, c, d, a, x[i+ 2], 23, -995338651); + + a = md5_ii(a, b, c, d, x[i+ 0], 6 , -198630844); + d = md5_ii(d, a, b, c, x[i+ 7], 10, 1126891415); + c = md5_ii(c, d, a, b, x[i+14], 15, -1416354905); + b = md5_ii(b, c, d, a, x[i+ 5], 21, -57434055); + a = md5_ii(a, b, c, d, x[i+12], 6 , 1700485571); + d = md5_ii(d, a, b, c, x[i+ 3], 10, -1894986606); + c = md5_ii(c, d, a, b, x[i+10], 15, -1051523); + b = md5_ii(b, c, d, a, x[i+ 1], 21, -2054922799); + a = md5_ii(a, b, c, d, x[i+ 8], 6 , 1873313359); + d = md5_ii(d, a, b, c, x[i+15], 10, -30611744); + c = md5_ii(c, d, a, b, x[i+ 6], 15, -1560198380); + b = md5_ii(b, c, d, a, x[i+13], 21, 1309151649); + a = md5_ii(a, b, c, d, x[i+ 4], 6 , -145523070); + d = md5_ii(d, a, b, c, x[i+11], 10, -1120210379); + c = md5_ii(c, d, a, b, x[i+ 2], 15, 718787259); + b = md5_ii(b, c, d, a, x[i+ 9], 21, -343485551); + + a = safe_add(a, olda); + b = safe_add(b, oldb); + c = safe_add(c, oldc); + d = safe_add(d, oldd); + } + return Array(a, b, c, d); +} + +function md5_cmn(q, a, b, x, s, t) { + return safe_add(bit_rol(safe_add(safe_add(a, q), safe_add(x, t)), s),b); +} + +function md5_ff(a, b, c, d, x, s, t) { + return md5_cmn((b & c) | ((~b) & d), a, b, x, s, t); +} + +function md5_gg(a, b, c, d, x, s, t) { + return md5_cmn((b & d) | (c & (~d)), a, b, x, s, t); +} + +function md5_hh(a, b, c, d, x, s, t) { + return md5_cmn(b ^ c ^ d, a, b, x, s, t); +} + +function md5_ii(a, b, c, d, x, s, t) { + return md5_cmn(c ^ (b | (~d)), a, b, x, s, t); +} + +function safe_add(x, y) { + var lsw = (x & 0xFFFF) + (y & 0xFFFF); + var msw = (x >> 16) + (y >> 16) + (lsw >> 16); + return (msw << 16) | (lsw & 0xFFFF); +} + +function bit_rol(num, cnt) { + return (num << cnt) | (num >>> (32 - cnt)); +} + +function str2binl(str) { + var bin = Array(); + var mask = (1 << 8) - 1; + for(var i = 0; i < str.length * 8; i += 8) + bin[i>>5] |= (str.charCodeAt(i / 8) & mask) << (i%32); + return bin; +} + +function binl2hex(binarray) { + var hex_tab = "0123456789abcdef"; + var str = ""; + for(var i = 0; i < binarray.length * 4; i++) { + str += hex_tab.charAt((binarray[i>>2] >> ((i%4)*8+4)) & 0xF) + + hex_tab.charAt((binarray[i>>2] >> ((i%4)*8 )) & 0xF); + } + return str; +} + +var plainText = "Rebellious subjects, enemies to peace,\n\ +Profaners of this neighbour-stained steel,--\n\ +Will they not hear? What, ho! you men, you beasts,\n\ +That quench the fire of your pernicious rage\n\ +With purple fountains issuing from your veins,\n\ +On pain of torture, from those bloody hands\n\ +Throw your mistemper'd weapons to the ground,\n\ +And hear the sentence of your moved prince.\n\ +Three civil brawls, bred of an airy word,\n\ +By thee, old Capulet, and Montague,\n\ +Have thrice disturb'd the quiet of our streets,\n\ +And made Verona's ancient citizens\n\ +Cast by their grave beseeming ornaments,\n\ +To wield old partisans, in hands as old,\n\ +Canker'd with peace, to part your canker'd hate:\n\ +If ever you disturb our streets again,\n\ +Your lives shall pay the forfeit of the peace.\n\ +For this time, all the rest depart away:\n\ +You Capulet; shall go along with me:\n\ +And, Montague, come you this afternoon,\n\ +To know our further pleasure in this case,\n\ +To old Free-town, our common judgment-place.\n\ +Once more, on pain of death, all men depart.\n" + +for (var i = 0; i < 4; ++i) { + plainText += plainText; +} + +assertEquals(hex_md5("abc"), "900150983cd24fb0d6963f7d28e17f72"); +for (var i = 0; i < 11; ++i) { + assertEquals(hex_md5(plainText), "1b8719c72d5d8bfd06e096ef6c6288c5"); +} -- 2.7.4