// 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 { struct TypedArrayElementsInfo { // Calculates the number of bytes required for specified number of elements. CalculateByteLength(lengthSmi: PositiveSmi): uintptr labels IfInvalid { const length = Convert<uintptr>(lengthSmi); const byteLength = length << this.sizeLog2; // If an overflow ocurred, the byte length exceeds // JSArrayBuffer::kMaxByteLength and is invalid. if (byteLength >>> this.sizeLog2 != length) goto IfInvalid; return byteLength; } // Calculates the maximum number of elements supported by a specified number // of bytes. CalculateLength(byteLength: uintptr): PositiveSmi labels IfInvalid { return TryUintPtrToPositiveSmi(byteLength >>> this.sizeLog2) otherwise IfInvalid; } // Determines if `bytes` (byte offset or length) cannot be evenly divided by // element size. IsUnaligned(bytes: uintptr): bool { // Exploits the fact the element size is a power of 2. Determining whether // there is remainder (not aligned) can be achieved efficiently with bit // masking. Shift is safe as sizeLog2 can be 3 at most (see // ElementsKindToShiftSize). return (bytes & ((1 << this.sizeLog2) - 1)) != 0; } sizeLog2: uintptr; map: Map; kind: ElementsKind; } extern runtime TypedArraySortFast(Context, Object): JSTypedArray; extern macro TypedArrayBuiltinsAssembler::ValidateTypedArray( Context, Object, constexpr string): JSTypedArray; extern macro TypedArrayBuiltinsAssembler::CallCMemcpy( RawPtr, RawPtr, uintptr): void; extern macro TypedArrayBuiltinsAssembler::CallCMemset( RawPtr, intptr, uintptr): void; extern macro TypedArrayBuiltinsAssembler::GetTypedArrayElementsInfo( JSTypedArray): TypedArrayElementsInfo; 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 %RawDownCast<LoadFn>(o); } UnsafeCast<StoreFn>(implicit context: Context)(o: Object): StoreFn { return %RawDownCast<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 CallCompare( implicit context: Context, array: JSTypedArray, comparefn: Callable)(a: Object, b: Object): Number { // 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)) { ThrowTypeError( context, kDetachedOperation, '%TypedArray%.prototype.sort'); } // c. If v is NaN, return +0. if (NumberIsNaN(v)) return 0; // d. return v. return v; } // Merges two sorted runs [from, middle) and [middle, to) // from "source" into "target". transitioning macro TypedArrayMerge( implicit context: Context, array: JSTypedArray, comparefn: Callable)( source: FixedArray, from: Smi, middle: Smi, to: Smi, target: FixedArray) { let left: Smi = from; let right: Smi = middle; for (let targetIndex: Smi = from; targetIndex < to; ++targetIndex) { if (left < middle && right >= to) { // If the left run has elements, but the right does not, we take // from the left. target.objects[targetIndex] = source.objects[left++]; } else if (left < middle) { // If both have elements, we need to compare. const leftElement: Object = source.objects[left]; const rightElement: Object = source.objects[right]; if (CallCompare(leftElement, rightElement) <= 0) { target.objects[targetIndex] = leftElement; left++; } else { target.objects[targetIndex] = rightElement; right++; } } else { // No elements on the left, but the right does, so we take // from the right. assert(left == middle); target.objects[targetIndex] = source.objects[right++]; } } } transitioning builtin TypedArrayMergeSort( implicit context: Context, array: JSTypedArray, comparefn: Callable)( source: FixedArray, from: Smi, to: Smi, target: FixedArray): Object { assert(to - from > 1); const middle: Smi = from + ((to - from) >> 1); // On the next recursion step source becomes target and vice versa. // This saves the copy of the relevant range from the original // array into a work array on each recursion step. if (middle - from > 1) TypedArrayMergeSort(target, from, middle, source); if (to - middle > 1) TypedArrayMergeSort(target, middle, to, source); TypedArrayMerge(source, from, middle, to, target); return Undefined; } // 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; // Arrays of length 1 or less are considered sorted. if (len < 2) return array; const comparefn: Callable = Cast<Callable>(comparefnObj) otherwise unreachable; 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; } } // Prepare the two work arrays. All numbers are converted to tagged // objects first, and merge sorted between the two FixedArrays. // The result is then written back into the JSTypedArray. const work1: FixedArray = AllocateZeroedFixedArray(Convert<intptr>(len)); const work2: FixedArray = AllocateZeroedFixedArray(Convert<intptr>(len)); for (let i: Smi = 0; i < len; ++i) { const element: Object = loadfn(context, array, i); work1.objects[i] = element; work2.objects[i] = element; } TypedArrayMergeSort(work2, 0, len, work1); // work1 contains the sorted numbers. Write them back. for (let i: Smi = 0; i < len; ++i) storefn(context, array, i, work1.objects[i]); return array; } }