• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright 2018 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5module typed_array {
6  extern runtime TypedArraySortFast(Context, Object): JSTypedArray;
7  extern macro ValidateTypedArray(
8      Context, Object, constexpr string): JSTypedArray;
9
10  extern macro LoadFixedTypedArrayElementAsTagged(
11      RawPtr, Smi, constexpr ElementsKind, constexpr ParameterMode): Object;
12  extern macro StoreFixedTypedArrayElementFromTagged(
13      Context, FixedTypedArrayBase, Smi, Object, constexpr ElementsKind,
14      constexpr ParameterMode);
15
16  type LoadFn = builtin(Context, JSTypedArray, Smi) => Object;
17  type StoreFn = builtin(Context, JSTypedArray, Smi, Object) => Object;
18
19  macro KindForArrayType<T : type>(): constexpr ElementsKind;
20  KindForArrayType<FixedUint8Array>(): constexpr ElementsKind {
21    return UINT8_ELEMENTS;
22  }
23  KindForArrayType<FixedInt8Array>(): constexpr ElementsKind {
24    return INT8_ELEMENTS;
25  }
26  KindForArrayType<FixedUint16Array>(): constexpr ElementsKind {
27    return UINT16_ELEMENTS;
28  }
29  KindForArrayType<FixedInt16Array>(): constexpr ElementsKind {
30    return INT16_ELEMENTS;
31  }
32  KindForArrayType<FixedUint32Array>(): constexpr ElementsKind {
33    return UINT32_ELEMENTS;
34  }
35  KindForArrayType<FixedInt32Array>(): constexpr ElementsKind {
36    return INT32_ELEMENTS;
37  }
38  KindForArrayType<FixedFloat32Array>(): constexpr ElementsKind {
39    return FLOAT32_ELEMENTS;
40  }
41  KindForArrayType<FixedFloat64Array>(): constexpr ElementsKind {
42    return FLOAT64_ELEMENTS;
43  }
44  KindForArrayType<FixedUint8ClampedArray>(): constexpr ElementsKind {
45    return UINT8_CLAMPED_ELEMENTS;
46  }
47  KindForArrayType<FixedBigUint64Array>(): constexpr ElementsKind {
48    return BIGUINT64_ELEMENTS;
49  }
50  KindForArrayType<FixedBigInt64Array>(): constexpr ElementsKind {
51    return BIGINT64_ELEMENTS;
52  }
53
54  builtin LoadFixedElement<T : type>(
55      context: Context, array: JSTypedArray, index: Smi): Object {
56    return LoadFixedTypedArrayElementAsTagged(
57        array.data_ptr, index, KindForArrayType<T>(), SMI_PARAMETERS);
58  }
59
60  builtin StoreFixedElement<T : type>(
61      context: Context, array: JSTypedArray, index: Smi,
62      value: Object): Object {
63    const elements: FixedTypedArrayBase =
64        unsafe_cast<FixedTypedArrayBase>(array.elements);
65    StoreFixedTypedArrayElementFromTagged(
66        context, elements, index, value, KindForArrayType<T>(), SMI_PARAMETERS);
67    return Undefined;
68  }
69
70  macro CallCompareWithDetachedCheck(
71      context: Context, array: JSTypedArray, comparefn: Callable, a: Object,
72      b: Object): Number labels Detached {
73    // a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)).
74    const v: Number =
75        ToNumber_Inline(context, Call(context, comparefn, Undefined, a, b));
76
77    // b. If IsDetachedBuffer(buffer) is true, throw a TypeError exception.
78    if (IsDetachedBuffer(array.buffer)) goto Detached;
79
80    // c. If v is NaN, return +0.
81    if (NumberIsNaN(v)) return 0;
82
83    // d. return v.
84    return v;
85  }
86
87  // InsertionSort is used for smaller arrays.
88  macro TypedArrayInsertionSort(
89      context: Context, array: JSTypedArray, from_arg: Smi, to_arg: Smi,
90      comparefn: Callable, Load: LoadFn, Store: StoreFn)
91  labels Detached {
92    let from: Smi = from_arg;
93    let to: Smi = to_arg;
94
95    if (IsDetachedBuffer(array.buffer)) goto Detached;
96
97    for (let i: Smi = from + 1; i < to; ++i) {
98      const element: Object = Load(context, array, i);
99      let j: Smi = i - 1;
100      for (; j >= from; --j) {
101        const tmp: Object = Load(context, array, j);
102        const order: Number = CallCompareWithDetachedCheck(
103            context, array, comparefn, tmp, element) otherwise Detached;
104        if (order > 0) {
105          Store(context, array, j + 1, tmp);
106        } else {
107          break;
108        }
109      }
110      Store(context, array, j + 1, element);
111    }
112  }
113
114  macro TypedArrayQuickSortImpl(
115      context: Context, array: JSTypedArray, from_arg: Smi, to_arg: Smi,
116      comparefn: Callable, Load: LoadFn, Store: StoreFn)
117  labels Detached {
118    let from: Smi = from_arg;
119    let to: Smi = to_arg;
120
121    while (to - from > 1) {
122      if (to - from <= 10) {
123        // TODO(szuend): Investigate InsertionSort removal.
124        //               Currently it does not make any difference when the
125        //               benchmarks are run locally.
126        TypedArrayInsertionSort(
127            context, array, from, to, comparefn, Load, Store)
128        otherwise Detached;
129        break;
130      }
131
132      // TODO(szuend): Check if a more involved third_index calculation is
133      //               worth it for very large arrays.
134      const third_index: Smi = from + ((to - from) >>> 1);
135
136      if (IsDetachedBuffer(array.buffer)) goto Detached;
137
138      // Find a pivot as the median of first, last and middle element.
139      let v0: Object = Load(context, array, from);
140      let v1: Object = Load(context, array, to - 1);
141      let v2: Object = Load(context, array, third_index);
142
143      const c01: Number = CallCompareWithDetachedCheck(
144          context, array, comparefn, v0, v1) otherwise Detached;
145      if (c01 > 0) {
146        // v1 < v0, so swap them.
147        let tmp: Object = v0;
148        v0 = v1;
149        v1 = tmp;
150      }
151      // v0 <= v1.
152      const c02: Number = CallCompareWithDetachedCheck(
153          context, array, comparefn, v0, v2) otherwise Detached;
154      if (c02 >= 0) {
155        // v2 <= v0 <= v1.
156        const tmp: Object = v0;
157        v0 = v2;
158        v2 = v1;
159        v1 = tmp;
160      } else {
161        // v0 <= v1 && v0 < v2.
162        const c12: Number = CallCompareWithDetachedCheck(
163            context, array, comparefn, v1, v2) otherwise Detached;
164        if (c12 > 0) {
165          // v0 <= v2 < v1.
166          const tmp: Object = v1;
167          v1 = v2;
168          v2 = tmp;
169        }
170      }
171
172      // v0 <= v1 <= v2.
173      Store(context, array, from, v0);
174      Store(context, array, to - 1, v2);
175
176      const pivot: Object = v1;
177      let low_end: Smi = from + 1;   // Upper bound of elems lower than pivot.
178      let high_start: Smi = to - 1;  // Lower bound of elems greater than pivot.
179
180      let low_end_value: Object = Load(context, array, low_end);
181      Store(context, array, third_index, low_end_value);
182      Store(context, array, low_end, pivot);
183
184      // From low_end to idx are elements equal to pivot.
185      // From idx to high_start are elements that haven"t been compared yet.
186      for (let idx: Smi = low_end + 1; idx < high_start; idx++) {
187        let element: Object = Load(context, array, idx);
188        let order: Number = CallCompareWithDetachedCheck(
189            context, array, comparefn, element, pivot) otherwise Detached;
190
191        if (order < 0) {
192          low_end_value = Load(context, array, low_end);
193          Store(context, array, idx, low_end_value);
194          Store(context, array, low_end, element);
195          low_end++;
196        } else if (order > 0) {
197          let break_for: bool = false;
198
199          while (order > 0) {
200            high_start--;
201            if (high_start == idx) {
202              break_for = true;
203              break;
204            }
205
206            const top_elem: Object = Load(context, array, high_start);
207            order = CallCompareWithDetachedCheck(
208                context, array, comparefn, top_elem, pivot) otherwise Detached;
209          }
210
211          if (break_for) {
212            break;
213          }
214
215          const high_start_value: Object = Load(context, array, high_start);
216          Store(context, array, idx, high_start_value);
217          Store(context, array, high_start, element);
218
219          if (order < 0) {
220            element = Load(context, array, idx);
221
222            low_end_value = Load(context, array, low_end);
223            Store(context, array, idx, low_end_value);
224            Store(context, array, low_end, element);
225            low_end++;
226          }
227        }
228      }
229
230      if ((to - high_start) < (low_end - from)) {
231        TypedArrayQuickSort(
232            context, array, high_start, to, comparefn, Load, Store);
233        to = low_end;
234      } else {
235        TypedArrayQuickSort(
236            context, array, from, low_end, comparefn, Load, Store);
237        from = high_start;
238      }
239    }
240  }
241
242  builtin TypedArrayQuickSort(
243      context: Context, array: JSTypedArray, from: Smi, to: Smi,
244      comparefn: Callable, Load: LoadFn, Store: StoreFn): JSTypedArray {
245    try {
246      TypedArrayQuickSortImpl(context, array, from, to, comparefn, Load, Store)
247      otherwise Detached;
248    }
249    label Detached {
250      ThrowTypeError(
251          context, kDetachedOperation, '%TypedArray%.prototype.sort');
252    }
253    return array;
254  }
255
256  // https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.sort
257  javascript builtin TypedArrayPrototypeSort(
258      context: Context, receiver: Object, ...arguments): JSTypedArray {
259    // 1. If comparefn is not undefined and IsCallable(comparefn) is false,
260    //    throw a TypeError exception.
261    const comparefn_obj: Object =
262        arguments.length > 0 ? arguments[0] : Undefined;
263    if (comparefn_obj != Undefined && !TaggedIsCallable(comparefn_obj)) {
264      ThrowTypeError(context, kBadSortComparisonFunction, comparefn_obj);
265    }
266
267    // 2. Let obj be the this value.
268    const obj: Object = receiver;
269
270    // 3. Let buffer be ? ValidateTypedArray(obj).
271    //    ValidateTypedArray currently returns the array, not the ViewBuffer.
272    const array: JSTypedArray =
273        ValidateTypedArray(context, obj, '%TypedArray%.prototype.sort');
274
275    // Default sorting is done in C++ using std::sort
276    if (comparefn_obj == Undefined) {
277      return TypedArraySortFast(context, obj);
278    }
279
280    // 4. Let len be obj.[[ArrayLength]].
281    const len: Smi = array.length;
282
283    try {
284      const comparefn: Callable =
285          cast<Callable>(comparefn_obj) otherwise CastError;
286      let loadfn: LoadFn;
287      let storefn: StoreFn;
288
289      let elements_kind: ElementsKind = array.elements_kind;
290
291      if (IsElementsKindGreaterThan(elements_kind, UINT32_ELEMENTS)) {
292        if (elements_kind == INT32_ELEMENTS) {
293          loadfn = LoadFixedElement<FixedInt32Array>;
294          storefn = StoreFixedElement<FixedInt32Array>;
295        } else if (elements_kind == FLOAT32_ELEMENTS) {
296          loadfn = LoadFixedElement<FixedFloat32Array>;
297          storefn = StoreFixedElement<FixedFloat32Array>;
298        } else if (elements_kind == FLOAT64_ELEMENTS) {
299          loadfn = LoadFixedElement<FixedFloat64Array>;
300          storefn = StoreFixedElement<FixedFloat64Array>;
301        } else if (elements_kind == UINT8_CLAMPED_ELEMENTS) {
302          loadfn = LoadFixedElement<FixedUint8ClampedArray>;
303          storefn = StoreFixedElement<FixedUint8ClampedArray>;
304        } else if (elements_kind == BIGUINT64_ELEMENTS) {
305          loadfn = LoadFixedElement<FixedBigUint64Array>;
306          storefn = StoreFixedElement<FixedBigUint64Array>;
307        } else if (elements_kind == BIGINT64_ELEMENTS) {
308          loadfn = LoadFixedElement<FixedBigInt64Array>;
309          storefn = StoreFixedElement<FixedBigInt64Array>;
310        } else {
311          unreachable;
312        }
313      } else {
314        if (elements_kind == UINT8_ELEMENTS) {
315          loadfn = LoadFixedElement<FixedUint8Array>;
316          storefn = StoreFixedElement<FixedUint8Array>;
317        } else if (elements_kind == INT8_ELEMENTS) {
318          loadfn = LoadFixedElement<FixedInt8Array>;
319          storefn = StoreFixedElement<FixedInt8Array>;
320        } else if (elements_kind == UINT16_ELEMENTS) {
321          loadfn = LoadFixedElement<FixedUint16Array>;
322          storefn = StoreFixedElement<FixedUint16Array>;
323        } else if (elements_kind == INT16_ELEMENTS) {
324          loadfn = LoadFixedElement<FixedInt16Array>;
325          storefn = StoreFixedElement<FixedInt16Array>;
326        } else if (elements_kind == UINT32_ELEMENTS) {
327          loadfn = LoadFixedElement<FixedUint32Array>;
328          storefn = StoreFixedElement<FixedUint32Array>;
329        } else {
330          unreachable;
331        }
332      }
333
334      TypedArrayQuickSort(context, array, 0, len, comparefn, loadfn, storefn);
335    }
336    label CastError {
337      unreachable;
338    }
339    return array;
340  }
341}
342