// Copyright 2018 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include 'src/builtins/builtins-typed-array-gen.h' namespace typed_array { extern runtime TypedArraySortFast(Context, Object): JSTypedArray; extern macro TypedArrayBuiltinsAssembler::ValidateTypedArray( Context, Object, constexpr string): JSTypedArray; extern macro LoadFixedTypedArrayElementAsTagged( RawPtr, Smi, constexpr ElementsKind, constexpr ParameterMode): Object; extern macro StoreFixedTypedArrayElementFromTagged( Context, FixedTypedArrayBase, Smi, Object, constexpr ElementsKind, constexpr ParameterMode); type LoadFn = builtin(Context, JSTypedArray, Smi) => Object; type StoreFn = builtin(Context, JSTypedArray, Smi, Object) => Object; // These UnsafeCast specializations are necessary becuase there is no // way to definitively test whether an Object is a Torque function // with a specific signature, and the default UnsafeCast implementation // would try to check this through an assert(Is<>), so the test // is bypassed in this specialization. UnsafeCast<LoadFn>(implicit context: Context)(o: Object): LoadFn { return %RawObjectCast<LoadFn>(o); } UnsafeCast<StoreFn>(implicit context: Context)(o: Object): StoreFn { return %RawObjectCast<StoreFn>(o); } macro KindForArrayType<T: type>(): constexpr ElementsKind; KindForArrayType<FixedUint8Array>(): constexpr ElementsKind { return UINT8_ELEMENTS; } KindForArrayType<FixedInt8Array>(): constexpr ElementsKind { return INT8_ELEMENTS; } KindForArrayType<FixedUint16Array>(): constexpr ElementsKind { return UINT16_ELEMENTS; } KindForArrayType<FixedInt16Array>(): constexpr ElementsKind { return INT16_ELEMENTS; } KindForArrayType<FixedUint32Array>(): constexpr ElementsKind { return UINT32_ELEMENTS; } KindForArrayType<FixedInt32Array>(): constexpr ElementsKind { return INT32_ELEMENTS; } KindForArrayType<FixedFloat32Array>(): constexpr ElementsKind { return FLOAT32_ELEMENTS; } KindForArrayType<FixedFloat64Array>(): constexpr ElementsKind { return FLOAT64_ELEMENTS; } KindForArrayType<FixedUint8ClampedArray>(): constexpr ElementsKind { return UINT8_CLAMPED_ELEMENTS; } KindForArrayType<FixedBigUint64Array>(): constexpr ElementsKind { return BIGUINT64_ELEMENTS; } KindForArrayType<FixedBigInt64Array>(): constexpr ElementsKind { return BIGINT64_ELEMENTS; } builtin LoadFixedElement<T: type>( context: Context, array: JSTypedArray, index: Smi): Object { return LoadFixedTypedArrayElementAsTagged( array.data_ptr, index, KindForArrayType<T>(), SMI_PARAMETERS); } builtin StoreFixedElement<T: type>( context: Context, array: JSTypedArray, index: Smi, value: Object): Object { const elements: FixedTypedArrayBase = UnsafeCast<FixedTypedArrayBase>(array.elements); StoreFixedTypedArrayElementFromTagged( context, elements, index, value, KindForArrayType<T>(), SMI_PARAMETERS); return Undefined; } transitioning macro CallCompareWithDetachedCheck( context: Context, array: JSTypedArray, comparefn: Callable, a: Object, b: Object): Number labels Detached { // a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)). const v: Number = ToNumber_Inline(context, Call(context, comparefn, Undefined, a, b)); // b. If IsDetachedBuffer(buffer) is true, throw a TypeError exception. if (IsDetachedBuffer(array.buffer)) goto Detached; // c. If v is NaN, return +0. if (NumberIsNaN(v)) return 0; // d. return v. return v; } // InsertionSort is used for smaller arrays. transitioning macro TypedArrayInsertionSort( context: Context, array: JSTypedArray, fromArg: Smi, toArg: Smi, comparefn: Callable, load: LoadFn, store: StoreFn) labels Detached { let from: Smi = fromArg; let to: Smi = toArg; if (IsDetachedBuffer(array.buffer)) goto Detached; for (let i: Smi = from + 1; i < to; ++i) { const element: Object = load(context, array, i); let j: Smi = i - 1; for (; j >= from; --j) { const tmp: Object = load(context, array, j); const order: Number = CallCompareWithDetachedCheck( context, array, comparefn, tmp, element) otherwise Detached; if (order > 0) { store(context, array, j + 1, tmp); } else { break; } } store(context, array, j + 1, element); } } transitioning macro TypedArrayQuickSortImpl( context: Context, array: JSTypedArray, fromArg: Smi, toArg: Smi, comparefn: Callable, load: LoadFn, store: StoreFn) labels Detached { let from: Smi = fromArg; let to: Smi = toArg; while (to - from > 1) { if (to - from <= 10) { // TODO(szuend): Investigate InsertionSort removal. // Currently it does not make any difference when the // benchmarks are run locally. TypedArrayInsertionSort( context, array, from, to, comparefn, load, store) otherwise Detached; break; } // TODO(szuend): Check if a more involved thirdIndex calculation is // worth it for very large arrays. const thirdIndex: Smi = from + ((to - from) >> 1); if (IsDetachedBuffer(array.buffer)) goto Detached; // Find a pivot as the median of first, last and middle element. let v0: Object = load(context, array, from); let v1: Object = load(context, array, to - 1); let v2: Object = load(context, array, thirdIndex); const c01: Number = CallCompareWithDetachedCheck( context, array, comparefn, v0, v1) otherwise Detached; if (c01 > 0) { // v1 < v0, so swap them. let tmp: Object = v0; v0 = v1; v1 = tmp; } // v0 <= v1. const c02: Number = CallCompareWithDetachedCheck( context, array, comparefn, v0, v2) otherwise Detached; if (c02 >= 0) { // v2 <= v0 <= v1. const tmp: Object = v0; v0 = v2; v2 = v1; v1 = tmp; } else { // v0 <= v1 && v0 < v2. const c12: Number = CallCompareWithDetachedCheck( context, array, comparefn, v1, v2) otherwise Detached; if (c12 > 0) { // v0 <= v2 < v1. const tmp: Object = v1; v1 = v2; v2 = tmp; } } // v0 <= v1 <= v2. store(context, array, from, v0); store(context, array, to - 1, v2); const pivot: Object = v1; let lowEnd: Smi = from + 1; // Upper bound of elems lower than pivot. let highStart: Smi = to - 1; // Lower bound of elems greater than pivot. let lowEndValue: Object = load(context, array, lowEnd); store(context, array, thirdIndex, lowEndValue); store(context, array, lowEnd, pivot); // From lowEnd to idx are elements equal to pivot. // From idx to highStart are elements that haven"t been compared yet. for (let idx: Smi = lowEnd + 1; idx < highStart; idx++) { let element: Object = load(context, array, idx); let order: Number = CallCompareWithDetachedCheck( context, array, comparefn, element, pivot) otherwise Detached; if (order < 0) { lowEndValue = load(context, array, lowEnd); store(context, array, idx, lowEndValue); store(context, array, lowEnd, element); lowEnd++; } else if (order > 0) { let breakFor: bool = false; while (order > 0) { highStart--; if (highStart == idx) { breakFor = true; break; } const topElement: Object = load(context, array, highStart); order = CallCompareWithDetachedCheck( context, array, comparefn, topElement, pivot) otherwise Detached; } if (breakFor) { break; } const highStartValue: Object = load(context, array, highStart); store(context, array, idx, highStartValue); store(context, array, highStart, element); if (order < 0) { element = load(context, array, idx); lowEndValue = load(context, array, lowEnd); store(context, array, idx, lowEndValue); store(context, array, lowEnd, element); lowEnd++; } } } if ((to - highStart) < (lowEnd - from)) { TypedArrayQuickSort( context, array, highStart, to, comparefn, load, store); to = lowEnd; } else { TypedArrayQuickSort( context, array, from, lowEnd, comparefn, load, store); from = highStart; } } } transitioning builtin TypedArrayQuickSort( context: Context, array: JSTypedArray, from: Smi, to: Smi, comparefn: Callable, load: LoadFn, store: StoreFn): JSTypedArray { try { TypedArrayQuickSortImpl(context, array, from, to, comparefn, load, store) otherwise Detached; } label Detached { ThrowTypeError( context, kDetachedOperation, '%TypedArray%.prototype.sort'); } return array; } // https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.sort transitioning javascript builtin TypedArrayPrototypeSort( context: Context, receiver: Object, ...arguments): JSTypedArray { // 1. If comparefn is not undefined and IsCallable(comparefn) is false, // throw a TypeError exception. const comparefnObj: Object = arguments.length > 0 ? arguments[0] : Undefined; if (comparefnObj != Undefined && !TaggedIsCallable(comparefnObj)) { ThrowTypeError(context, kBadSortComparisonFunction, comparefnObj); } // 2. Let obj be the this value. const obj: Object = receiver; // 3. Let buffer be ? ValidateTypedArray(obj). // ValidateTypedArray currently returns the array, not the ViewBuffer. const array: JSTypedArray = ValidateTypedArray(context, obj, '%TypedArray%.prototype.sort'); // Default sorting is done in C++ using std::sort if (comparefnObj == Undefined) { return TypedArraySortFast(context, obj); } // 4. Let len be obj.[[ArrayLength]]. const len: Smi = array.length; try { const comparefn: Callable = Cast<Callable>(comparefnObj) otherwise CastError; let loadfn: LoadFn; let storefn: StoreFn; let elementsKind: ElementsKind = array.elements_kind; if (IsElementsKindGreaterThan(elementsKind, UINT32_ELEMENTS)) { if (elementsKind == INT32_ELEMENTS) { loadfn = LoadFixedElement<FixedInt32Array>; storefn = StoreFixedElement<FixedInt32Array>; } else if (elementsKind == FLOAT32_ELEMENTS) { loadfn = LoadFixedElement<FixedFloat32Array>; storefn = StoreFixedElement<FixedFloat32Array>; } else if (elementsKind == FLOAT64_ELEMENTS) { loadfn = LoadFixedElement<FixedFloat64Array>; storefn = StoreFixedElement<FixedFloat64Array>; } else if (elementsKind == UINT8_CLAMPED_ELEMENTS) { loadfn = LoadFixedElement<FixedUint8ClampedArray>; storefn = StoreFixedElement<FixedUint8ClampedArray>; } else if (elementsKind == BIGUINT64_ELEMENTS) { loadfn = LoadFixedElement<FixedBigUint64Array>; storefn = StoreFixedElement<FixedBigUint64Array>; } else if (elementsKind == BIGINT64_ELEMENTS) { loadfn = LoadFixedElement<FixedBigInt64Array>; storefn = StoreFixedElement<FixedBigInt64Array>; } else { unreachable; } } else { if (elementsKind == UINT8_ELEMENTS) { loadfn = LoadFixedElement<FixedUint8Array>; storefn = StoreFixedElement<FixedUint8Array>; } else if (elementsKind == INT8_ELEMENTS) { loadfn = LoadFixedElement<FixedInt8Array>; storefn = StoreFixedElement<FixedInt8Array>; } else if (elementsKind == UINT16_ELEMENTS) { loadfn = LoadFixedElement<FixedUint16Array>; storefn = StoreFixedElement<FixedUint16Array>; } else if (elementsKind == INT16_ELEMENTS) { loadfn = LoadFixedElement<FixedInt16Array>; storefn = StoreFixedElement<FixedInt16Array>; } else if (elementsKind == UINT32_ELEMENTS) { loadfn = LoadFixedElement<FixedUint32Array>; storefn = StoreFixedElement<FixedUint32Array>; } else { unreachable; } } TypedArrayQuickSort(context, array, 0, len, comparefn, loadfn, storefn); } label CastError { unreachable; } return array; } }