/* * Copyright (c) 2023, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package org.openjdk.bench.java.lang.foreign; import java.lang.foreign.Arena; import java.lang.foreign.MemorySegment; import java.lang.foreign.ValueLayout; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Fork; import org.openjdk.jmh.annotations.Measurement; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OutputTimeUnit; import org.openjdk.jmh.annotations.Setup; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.annotations.TearDown; import org.openjdk.jmh.annotations.Warmup; import org.openjdk.jmh.annotations.CompilerControl; import sun.misc.Unsafe; import java.nio.ByteBuffer; import java.nio.ByteOrder; import java.util.concurrent.TimeUnit; import static java.lang.foreign.ValueLayout.*; import static org.openjdk.jmh.annotations.CompilerControl.Mode.*; @BenchmarkMode(Mode.AverageTime) @Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS) @Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS) @State(org.openjdk.jmh.annotations.Scope.Thread) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Fork(value = 3, jvmArgsAppend = { "--enable-preview", "--enable-native-access=ALL-UNNAMED" }) public class BinarySearch extends JavaLayouts { static final Unsafe UNSAFE = Utils.unsafe; static final MemorySegment ALL = MemorySegment.NULL.reinterpret(Long.MAX_VALUE); static final ValueLayout.OfChar CHAR_LE = JAVA_CHAR_UNALIGNED.withOrder(ByteOrder.LITTLE_ENDIAN); private long mPage; private byte[] key; @Setup public void setup() { mPage = Arena.global().allocate(NODE_DATA.length).address(); key = KEY; MemorySegment.copy(NODE_DATA, 0, ALL, ValueLayout.JAVA_BYTE, mPage, NODE_DATA.length); } @Benchmark public int binarySearch_panama() { byte[] key = this.key; final var page = mPage; final int keyLen = key.length; final int startPos = p_searchVecStart(); int lowPos = startPos; int highPos = p_searchVecEnd(); int lowMatch = 0; int highMatch = 0; outer: while (lowPos <= highPos) { int midPos = ((lowPos + highPos) >> 1) & ~1; int compareLoc = p_ushortGetLE(page, midPos); int compareLen = p_byteGet(page, compareLoc++); if (compareLen >= 0) { compareLen++; } int minLen = Math.min(compareLen, keyLen); int i = Math.min(lowMatch, highMatch); for (; i keyLen) { highPos = midPos - 2; highMatch = i; } else { return midPos - startPos; } } return ~(lowPos - startPos); } @Benchmark public int binarySearch_unsafe() { byte[] key = this.key; final var page = mPage; final int keyLen = key.length; final int startPos = u_searchVecStart(); int lowPos = startPos; int highPos = u_searchVecEnd(); int lowMatch = 0; int highMatch = 0; outer: while (lowPos <= highPos) { int midPos = ((lowPos + highPos) >> 1) & ~1; int compareLoc = u_ushortGetLE(page, midPos); int compareLen = u_byteGet(page, compareLoc++); if (compareLen >= 0) { compareLen++; } int minLen = Math.min(compareLen, keyLen); int i = Math.min(lowMatch, highMatch); for (; i keyLen) { highPos = midPos - 2; highMatch = i; } else { return midPos - startPos; } } return ~(lowPos - startPos); } int u_searchVecStart() { return u_ushortGetLE(mPage, 8); } int u_searchVecEnd() { return u_ushortGetLE(mPage, 10); } static byte u_byteGet(long page, int index) { return UNSAFE.getByte(page + index); } static int u_ushortGetLE(long page, int index) { return UNSAFE.getChar(page + index); } int p_searchVecStart() { return p_ushortGetLE(mPage, 8); } int p_searchVecEnd() { return p_ushortGetLE(mPage, 10); } static byte p_byteGet(long page, int index) { return ALL.get(JAVA_BYTE, page + index); } static int p_ushortGetLE(long page, int index) { return ALL.get(CHAR_LE, page + index); } /** * A key which should be in the leaf node. */ static final byte[] KEY = {79, 5, 110, 83, -66, 29, 63, -70}; /** * 4096-byte b-tree leaf node with 300 random 8-byte keys which refer to 0-byte values. */ static final byte[] NODE_DATA = { -118, 0, 0, 0, -44, 5, 15, 10, -62, 6, 24, 9, 7, -85, 102, -2, -87, 1, -75, 104, -61, 0, 7, -92, 59, -8, 99, 36, -33, 114, 55, 0, 7, -61, -124, -24, -65, 47, 62, 86, 110, 0, 7, -31, 5, -71, 124, 58, -70, 111, 122, 0, 7, 52, 76, -77, 63, 95, 95, 32, -94, 0, 7, -92, 23, 95, -112, 100, -76, -107, 104, 0, 7, -4, -62, -82, 126, -128, -46, -86, -104, 0, 7, -102, -14, 8, -85, -5, 62, -15, 123, 0, 7, 94, -117, -109, -32, 52, -99, -128, 31, 0, 7, 4, 34, 47, -30, 31, 80, 105, 21, 0, 7, 60, -125, 46, -105, -118, -57, 19, -74, 0, 7, -91, 51, -33, -109, -91, -106, 4, 8, 0, 7, -118, -111, 89, 78, -31, 104, 32, 103, 0, 7, -68, 21, 25, 97, -124, -30, -26, -22, 0, 7, -32, 38, -47, -19, 27, 69, -91, -76, 0, 7, -107, -44, -11, 111, -6, -36, -36, 123, 0, 7, 8, 116, -14, 49, 63, -82, -79, 93, 0, 7, 97, -91, 27, 110, 51, -1, -52, -13, 0, 7, 29, 92, -25, -31, 76, -113, -124, -30, 0, 7, -31, 75, 55, 11, 93, -2, 93, -10, 0, 7, -5, 120, -4, -67, 13, -119, -71, -125, 0, 7, 93, -96, 85, 44, 35, -109, -75, -19, 0, 7, -25, -104, -28, 12, -32, -110, 41, -76, 0, 7, -4, -82, -4, -26, -119, -10, 62, -16, 0, 7, -55, -71, -9, -79, 77, -121, -81, 120, 0, 7, -123, -58, 88, 104, 116, -64, -116, 39, 0, 7, 53, 21, 1, 92, -34, 46, -66, 100, 0, 7, -47, -20, -4, 40, 77, 116, -39, 62, 0, 7, -85, 18, 42, 107, 103, -10, 11, -19, 0, 7, 54, -101, 55, 31, 63, 2, 24, -94, 0, 7, 107, -49, -112, -29, -98, 96, -18, 61, 0, 7, -53, 84, 67, -116, 103, -63, 106, 49, 0, 7, 19, 77, -86, -115, -24, -114, -42, 111, 0, 7, -10, -110, 0, 68, -124, 126, -90, 88, 0, 7, 11, -114, -115, 19, -111, 7, -18, -83, 0, 7, 1, 75, -76, 31, 58, -25, 86, -65, 0, 7, -12, 72, 127, 2, -14, -80, -103, -57, 0, 7, 124, -128, -65, 22, 116, -126, -65, -67, 0, 7, 52, 113, -36, -120, -107, 25, 125, -119, 0, 7, -73, -118, -97, -61, -102, 22, 92, -119, 0, 7, 119, -114, 105, -15, -72, -126, 18, 103, 0, 7, -105, -121, 111, 127, 7, 115, 8, -94, 0, 7, -12, 27, -57, -126, -35, 25, 107, 69, 0, 7, -98, -76, -54, -14, 44, 56, 26, -92, 0, 7, -125, 57, -77, -108, 40, -63, -80, -23, 0, 7, -57, -77, -38, -72, 85, 41, -92, 52, 0, 7, -109, 72, 37, -1, -24, -91, 59, 61, 0, 7, 24, -31, 116, 43, -112, -119, -11, -49, 0, 7, -78, -1, 5, 13, -23, 87, -40, 86, 0, 7, -87, 6, 12, -31, -60, -105, 44, -37, 0, 7, 4, 11, 35, 20, 87, -116, -12, 90, 0, 7, -100, 109, 11, -14, -104, -13, 81, 79, 0, 7, -1, 19, -70, 73, 45, -46, 85, -36, 0, 7, -101, 52, 110, 43, -6, -41, 77, -127, 0, 7, -7, 120, -56, 16, -24, -35, 21, 123, 0, 7, 124, -57, 46, 87, 77, -61, -118, 102, 0, 7, -42, 89, -42, 108, -103, -32, 17, -46, 0, 7, -48, -41, -24, 48, 32, -100, -110, -57, 0, 7, -22, -26, 2, -122, 79, -20, -93, 52, 0, 7, 96, -115, 75, 15, -7, -110, 50, -31, 0, 7, -45, -48, 66, 97, 20, -12, 62, -124, 0, 7, 7, -21, 43, 91, 24, 82, -67, -20, 0, 7, -39, -96, 104, 92, -27, 11, -119, -118, 0, 7, 111, -108, -66, 18, -29, 84, -77, 105, 0, 7, -80, 6, 99, 51, 106, -53, 66, 123, 0, 7, -9, -69, 124, 77, 100, -111, -21, -41, 0, 7, -87, -82, -61, 78, 70, -86, -57, 63, 0, 7, -71, -112, 84, 18, -81, 1, -12, 85, 0, 7, -30, -124, -17, -55, -79, 94, -128, -116, 0, 7, -63, -104, -35, -99, 21, -35, -104, 39, 0, 7, -125, -128, 98, 100, -81, -99, -29, -17, 0, 7, 3, 99, -97, 71, -27, -94, -37, 17, 0, 7, 56, -113, -94, -23, 94, 97, -79, 78, 0, 7, 79, 5, 110, 83, -66, 29, 63, -70, 0, 7, -103, -3, 35, 5, -15, 114, -15, -41, 0, 7, -100, 8, -77, -30, -45, 108, 4, -85, 0, 7, -20, 90, -76, 44, -27, 104, -128, -88, 0, 7, -119, -57, -12, 62, -99, -109, -41, 74, 0, 7, 103, 14, -102, -119, 80, -121, 7, 94, 0, 7, 120, 60, 33, -105, 116, -101, 95, 82, 0, 7, 76, -46, -71, -107, -12, -88, -128, -47, 0, 7, -91, 88, 27, -125, 54, 69, 58, -100, 0, 7, 87, -81, -48, 23, 24, 6, -32, 121, 0, 7, -53, -31, 30, 73, 27, -94, -5, -14, 0, 7, 93, 90, 33, 29, 59, -21, 108, -8, 0, 7, 117, 111, -21, -112, -43, 29, 68, 49, 0, 7, 107, -113, 44, -26, 23, 113, 82, -36, 0, 7, -92, -31, -18, 84, -51, 31, 25, 52, 0, 7, 60, 115, 91, -33, -82, -11, -99, -23, 0, 7, -12, -50, -110, -44, 75, -75, 0, 48, 0, 7, 69, 42, -20, -96, -105, 65, 81, 16, 0, 7, -73, -49, 81, 31, -87, 91, -32, -14, 0, 7, 114, 90, 73, -98, -65, -8, -73, 109, 0, 7, 21, -105, 11, 77, -122, 116, 52, 71, 0, 7, -58, 29, -7, -122, -105, 35, -120, -69, 0, 7, -112, -124, 85, -117, -104, 91, -110, -79, 0, 7, -101, -37, -20, -93, -75, -43, 58, -79, 0, 7, 21, 72, 57, -28, -98, -27, 98, -39, 0, 7, -25, -71, -94, -99, -71, -20, 47, 39, 0, 7, 21, -126, -115, 75, -118, 32, 26, -98, 0, 7, 99, 108, 43, 0, -23, -120, 96, -86, 0, 7, -81, 76, 117, 117, -85, -30, 38, 18, 0, 7, 112, -67, -115, -42, -67, 54, -8, 17, 0, 7, 99, 102, -124, -110, -94, 96, -127, 88, 0, 7, 87, 124, 101, 66, -77, -53, 27, -99, 0, 7, 3, -7, 18, 5, 103, -80, -30, 50, 0, 7, 19, -4, -40, 88, -44, 97, -120, -46, 0, 7, -125, -87, -66, -103, 117, 111, -12, -41, 0, 7, 48, 25, -42, -87, 45, -97, -5, -15, 0, 7, -84, 43, -29, -63, -116, 3, 15, -24, 0, 7, 81, 88, -38, 85, 80, -78, -49, 35, 0, 7, -104, -56, 53, 7, 45, -33, 72, 95, 0, 7, -85, 84, 48, 16, -48, 94, 106, 124, 0, 7, 56, 53, -37, 123, 33, -42, 121, -85, 0, 7, -121, 126, -4, 8, -56, 25, -47, -76, 0, 7, -50, -72, -15, 61, -13, -127, -92, 74, 0, 7, -60, 41, -77, 11, 85, 54, -12, -111, 0, 7, -74, -10, 27, 27, 108, 75, -123, 126, 0, 7, -115, 26, -99, -32, -110, -107, 83, 117, 0, 7, -1, -120, 90, 94, 113, 0, -42, 29, 0, 7, -7, 93, -10, 120, -19, -49, -69, -124, 0, 7, 58, 35, 33, -70, 95, -42, -61, -92, 0, 7, 73, 18, 81, -49, 117, -63, -12, 100, 0, 7, -87, 1, 87, -73, 85, -47, 18, -110, 0, 7, 74, 113, 56, -2, 8, 94, -105, 84, 0, 7, 65, 106, 57, -79, 22, -49, -48, 73, 0, 7, -69, 37, 120, 92, 108, -23, 23, -40, 0, 7, -72, -110, 75, 10, -18, 25, 31, 16, 0, 7, -46, -11, -107, -22, -55, -113, -62, -45, 0, 7, 5, 123, 65, -98, 85, -72, -116, 5, 0, 7, 17, 30, 63, -35, 68, 30, -38, -109, 0, 7, 53, 116, -44, -62, -125, 99, -76, 86, 0, 7, -38, 125, 94, 117, 109, -26, -84, -28, 0, 7, 0, 63, 79, 125, 103, -93, -106, 115, 0, 7, -90, 64, -62, 28, 14, 33, 122, -61, 0, 7, -96, 19, -79, -102, -62, 11, -53, -111, 0, 7, -99, -53, -34, 99, -14, -99, 19, -106, 0, 7, 108, 51, 106, 26, 96, -61, -29, -46, 0, 7, -9, 6, 51, 13, 91, 18, 18, 13, 0, 7, 32, -39, 7, 28, 39, -61, -12, 87, 0, 7, 45, 55, 65, -45, -18, 8, -68, -101, 0, 7, -106, 101, -62, 101, 8, -16, -40, -100, 0, 7, 32, -106, -120, -115, 125, 92, -3, 117, 0, 7, 42, -21, -82, 49, -57, -20, 62, -52, 0, 7, 70, -36, 94, -120, -37, -60, 62, 77, 0, 7, 11, -48, -119, -94, 106, -123, -44, -108, 0, 7, -113, -123, -70, -47, 13, 13, -61, 42, 0, 7, -68, -12, 85, -113, -67, 19, -95, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62, 5, 66, 10, -50, 15, 106, 1, 116, 15, -82, 12, -70, 15, 68, 13, -46, 2, -42, 12, 38, 4, 0, 2, 102, 0, -120, 15, -10, 10, 22, 5, 94, 12, -34, 14, 110, 2, 54, 12, -90, 10, -84, 0, 18, 13, 112, 14, -86, 11, 92, 14, 46, 10, 96, 1, 52, 14, -74, 5, 72, 14, -80, 15, -4, 14, -40, 15, 32, 5, 124, 12, -64, 14, 76, 1, 48, 4, -42, 3, -22, 3, -82, 3, 8, 13, -14, 14, -36, 11, -54, 14, -30, 1, -102, 12, -72, 12, -64, 0, -104, 5, 122, 5, 26, 15, -126, 11, 126, 15, 98, 13, -2, 12, 16, 10, -94, 5, -100, 10, -124, 5, -8, 13, -40, 10, 68, 4, 58, 13, 102, 14, -26, 11, 52, 0, -120, 1, -28, 13, 16, 1, 42, 5, 118, 13, 46, 1, 84, 12, 12, 14, 118, 4, -36, 2, -58, 4, 96, 15, 124, 3, 112, 0, -18, 4, -38, 13, -18, 13, -112, 3, -84, 5, -48, 4, -16, 11, -92, 12, -28, 4, -6, 11, 44, 3, 80, 11, -74, 14, -26, 2, -60, 10, 88, 4, -120, 10, 50, 11, 82, 14, -110, 10, -84, 14, -90, 15, 28, 4, 64, 3, 56, 15, 22, 14, -30, 10, 122, 14, 84, 3, -34, 0, -44, 14, 92, 0, 42, 14, -116, 11, 90, 2, -78, 13, -74, 0, 108, 13, 38, 13, 18, 4, -12, 3, 4, 12, -112, 12, -50, 10, 24, 3, 16, 15, 32, 14, 20, 11, 104, 3, 56, 1, 102, 5, -20, 10, 110, 11, 2, 14, 100, 11, -126, 2, 8, 4, -92, 3, -114, 14, 60, 11, 126, 10, 94, 3, -100, 1, -122, 12, 34, 3, 26, 10, 28, 13, 126, 1, 50, 2, -94, 14, -96, 11, 46, 15, -58, 13, 66, 15, -60, 1, -56, 2, 58, 4, -24, 14, 6, 1, -66, 11, -106, 11, -128, 4, 14, 3, 24, 12, -100, 15, -124, 0, -32, 12, 56, 10, -88, 4, 10, 11, 86, 10, -64, 5, -62, 3, 62, 14, 0, 11, 40, 11, -40, 1, -94, 0, -114, 5, -90, 1, 98, 4, -16, 2, -20, 15, 76, 10, 82, 0, 30, 2, -52, 3, -6, 2, 10, 2, -60, 15, 92, 5, -70, 1, 88, 13, 82, 5, 96, 10, -30, 15, 76, 15, 62, 0, 22, 0, 114, 3, 122, 0, 54, 3, 72, 5, -38, 4, -10, 1, -96, 2, 36, 1, 108, 4, 12, 0, 78, 4, 70, 11, -2, 3, -116, 2, -118, 13, -20, 1, 44, 12, -98, 4, -80, 10, -110, 1, -102, 3, -70, 10, 30, 11, 2, 5, -86, 2, -8, 4, -114, 0, -54, 5, -66, 2, 32, 0, -108, 4, -76, 11, -72, 3, -50, 1, -10, 15, -4, 0, -68, 13, 66, 1, 86, 15, 74, 3, 106, 15, -118, 4, -62, 12, 70, 2, -110, 15, -46, 11, 26, 1, 12, 5, 100, 2, -124, 14, 14, 12, 60, 2, 116, 10, -56, 11, 120, 2, 52, 5, 78, 13, -88, 13, -98, 13, -104, 0, 6, 15, 42, 0, -54, 0, 114, 12, -128, 13, -108, 13, -76, 2, 74, 12, -48, 13, -22, 12, 106, 10, 64, 12, -24, 0, -32, 3, 36, 15, 80, 2, 48, 13, 4, 3, 120, 11, 104, 12, -52, 12, 90, 11, -80, 1, 116, 1, 34, 12, -122, 3, 86, 1, 112, 5, -106, 2, 36, 10, -68, 4, 40, 2, -104, 14, -44, 0, -14, 0, 72, 0, -12, 12, 20, 2, -78, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 40, -1, -63, -113, 100, -13, -38, -6, 0, 7, 121, 17, 63, -127, 123, -47, 85, -50, 0, 7, -8, -27, -38, -14, -37, -6, 96, 63, 0, 7, 11, 98, 70, 125, 95, -35, 118, 114, 0, 7, -115, 13, -35, -71, 18, 46, -10, 93, 0, 7, 0, -82, 73, 32, -72, 37, 14, -15, 0, 7, -102, -26, -29, -73, -27, 109, 118, -87, 0, 7, -113, 47, -87, 0, 91, -76, -82, 85, 0, 7, -95, 48, -10, 99, -88, 0, 84, 124, 0, 7, -27, -54, 44, 42, 0, 40, -80, 16, 0, 7, -41, 93, -122, 9, 87, -5, 89, 59, 0, 7, 115, -33, -16, -48, -77, 34, 34, 75, 0, 7, 81, 91, 57, 113, 102, -95, 33, -62, 0, 7, 84, 34, -65, 2, -95, -66, -113, -124, 0, 7, 43, -119, -64, 100, -112, 82, -20, -17, 0, 7, 8, 58, -59, 4, 1, -21, 53, 50, 0, 7, -73, 18, -30, -106, -61, -115, 61, -96, 0, 7, -72, 61, -26, 36, 43, -114, -126, 82, 0, 7, 80, 1, -3, 1, 48, 125, 44, -120, 0, 7, 102, -53, 112, 54, 40, 5, 53, 72, 0, 7, 47, -81, 39, -61, -122, -105, 113, -19, 0, 7, 90, -117, -124, -60, -36, -107, -32, 20, 0, 7, 108, -9, -48, -82, -94, 30, 117, 127, 0, 7, 4, -5, -118, 29, 40, 77, -14, -29, 0, 7, -111, -21, 5, -110, -118, -122, 88, 126, 0, 7, -114, -64, -85, 124, 86, 125, -26, 82, 0, 7, 107, 17, 32, -8, 3, 87, -79, 9, 0, 7, -72, 76, -10, -38, -76, -79, 91, 51, 0, 7, -110, 20, 70, 107, 47, 6, -38, -27, 0, 7, 82, -20, -47, 87, 23, 34, -125, -44, 0, 7, 115, -93, -55, 74, 113, -74, 119, -78, 0, 7, -84, -92, -47, -77, -24, 101, 74, -90, 0, 7, 78, 7, -20, -20, 87, 12, 27, 67, 0, 7, -15, -28, 85, 57, 85, 99, -88, 123, 0, 7, 110, -54, 80, -62, -36, 0, 111, 34, 0, 7, 109, 21, -68, -62, -90, -106, 70, -52, 0, 7, -16, 49, -79, 85, -56, -18, 67, 77, 0, 7, 34, 87, -12, -128, -117, -106, 104, 104, 0, 7, 96, 79, -100, -101, -115, -45, -35, 21, 0, 7, -121, 23, -125, 61, 24, -65, 22, 103, 0, 7, -128, 97, -52, 55, -63, -93, 111, -14, 0, 7, 9, 70, 86, -111, 68, -7, -10, 94, 0, 7, -59, -79, 123, -114, -98, -102, 62, 79, 0, 7, -122, 89, 111, -95, 107, 18, -94, -115, 0, 7, -40, 65, -31, 2, -126, 25, -103, 31, 0, 7, -47, 37, -40, 48, -50, -93, -77, 70, 0, 7, 24, 73, -21, -58, 111, 23, -1, -114, 0, 7, 51, -127, -104, -10, 16, -118, 18, -46, 0, 7, 73, -33, 42, -75, -54, 44, -117, 116, 0, 7, 74, -15, 114, 105, -79, 71, -67, -85, 0, 7, 100, 67, 56, -6, -115, -92, 74, 17, 0, 7, -43, -16, 7, 10, -107, -69, -80, 116, 0, 7, -119, -7, -11, -30, 69, 10, -121, 120, 0, 7, -12, -60, 44, 117, -44, 88, -122, 126, 0, 7, -74, 108, -52, -24, 10, 107, 60, 80, 0, 7, 8, 13, -19, -100, 73, 75, -96, -21, 0, 7, -26, 14, 5, -57, -85, 47, 50, 13, 0, 7, -29, -72, -16, -62, 45, -117, -42, 0, 0, 7, 54, -80, -34, 5, -45, -57, -119, -21, 0, 7, 5, -63, 27, 84, -4, -42, 40, 87, 0, 7, -16, -7, -125, -42, 1, -76, 105, -65, 0, 7, -31, 102, 86, 65, 20, 53, -27, 111, 0, 7, 17, -9, 43, -98, 87, -58, -11, -49, 0, 7, 119, -82, 74, 121, -23, -9, 1, -75, 0, 7, 101, 68, 114, -50, -54, 97, -18, 60, 0, 7, 27, -121, -68, 101, -66, 73, -60, -70, 0, 7, 74, 42, 71, -83, 89, 41, -46, 95, 0, 7, 2, -63, -108, 26, 54, -53, 60, 66, 0, 7, 28, -93, -93, -23, -73, 112, -83, 114, 0, 7, -48, -43, 67, 33, -74, 69, 116, -92, 0, 7, -15, 49, 47, -95, 7, -100, 69, -50, 0, 7, 3, -39, -76, 107, 78, -59, 117, 118, 0, 7, -116, 124, -47, -117, 93, -74, 109, 29, 0, 7, -28, -5, 23, -117, 94, -34, -94, 27, 0, 7, -2, -73, 92, 79, 111, -117, -104, 105, 0, 7, 39, -118, 32, -100, 101, 121, 108, 42, 0, 7, 23, -45, -51, 82, 113, 113, 94, -19, 0, 7, 8, -128, 35, -82, -81, 87, -64, -77, 0, 7, 123, 64, -3, -81, 37, -43, 75, -53, 0, 7, 98, -73, 102, -47, -26, -89, -49, -72, 0, 7, -21, -6, -54, -53, 40, 93, -34, -88, 0, 7, 48, -59, 91, 101, -54, -88, 66, 14, 0, 7, 2, -8, -110, -13, 49, -53, -99, -9, 0, 7, -38, -124, 7, 10, 115, 101, 89, -124, 0, 7, -97, 63, 20, 78, -4, 8, 121, 0, 0, 7, 39, 85, 36, -84, -92, 11, 4, 10, 0, 7, 98, -90, -37, -36, -86, -111, -2, 47, 0, 7, 53, -87, -111, 2, -120, -23, -102, 30, 0, 7, -31, -121, 112, 50, -23, -12, 68, -105, 0, 7, -80, 97, 80, -63, -22, 57, -89, -20, 0, 7, -30, 24, 91, -92, -108, -104, -5, -48, 0, 7, -34, -2, 17, -6, 83, 53, 19, -92, 0, 7, -34, -30, 19, -94, 75, -52, -89, -10, 0, 7, 97, 85, 113, 121, -65, 79, 57, 94, 0, 7, -54, -128, 111, 46, -37, 75, 125, 85, 0, 7, -127, 125, -65, 106, 66, -95, -33, 101, 0, 7, -28, -98, -41, 13, 69, -111, 2, -95, 0, 7, 65, -43, -10, 78, 18, -83, -122, -5, 0, 7, 52, -82, -94, 97, 13, -58, 64, 106, 0, 7, 68, 110, -67, -87, 28, -72, 15, 102, 0, 7, 45, 111, -37, 115, -34, 112, -117, -94, 0, 7, 109, 84, 101, -100, 44, -108, 1, 77, 0, 7, 55, -120, 66, -25, 62, -76, -110, -75, 0, 7, 89, -45, 101, -112, 117, -99, 106, -36, 0, 7, 106, -116, 10, -34, -7, -107, 16, 2, 0, 7, 95, -106, 101, 121, 121, -126, -1, 33, 0, 7, 11, -69, 55, -12, 8, -11, -40, 89, 0, 7, -111, -117, -92, 48, 34, -61, 19, -71, 0, 7, 12, 82, 59, 121, -34, 115, 123, 120, 0, 7, 83, -120, -42, 71, -92, -80, -83, 96, 0, 7, 10, -118, 37, 3, -9, -127, 57, 82, 0, 7, 48, -3, 47, 1, 73, 2, -39, 3, 0, 7, 8, -46, 54, 8, -125, -28, 88, 54, 0, 7, 92, -126, -61, -99, 63, 90, 14, 45, 0, 7, -45, -30, 118, -91, 127, -9, -50, -32, 0, 7, 115, 77, -68, -59, -61, 80, -61, -4, 0, 7, -6, -54, 82, 46, 21, -124, 0, 23, 0, 7, 125, 55, 88, 73, 1, -36, -92, 77, 0, 7, 84, -53, 30, -67, 16, 36, 87, -55, 0, 7, 78, 45, 83, 7, -127, -19, 95, -23, 0, 7, 17, -6, -120, 94, 73, 64, -70, 13, 0, 7, 24, 115, 97, 15, 64, -71, 126, 97, 0, 7, 94, 50, -37, -11, -38, -62, -73, -99, 0, 7, 6, -48, 37, -44, 70, 81, 103, -17, 0, 7, -124, -19, 103, -47, -13, 8, -112, -78, 0, 7, 24, 44, 7, -54, -82, 94, 107, 63, 0, 7, 15, -4, -113, 1, -109, 67, 23, -123, 0, 7, -32, 73, 51, 64, -8, 89, 73, 71, 0, 7, 103, 52, 29, 99, -3, 28, 107, -102, 0, 7, 34, 74, 21, 108, 91, 46, -99, -100, 0, 7, -24, -128, 88, -96, 89, -10, -95, 31, 0, 7, -128, -68, -73, 42, -11, -92, -13, 47, 0, 7, 88, 27, -35, 111, 85, 47, 20, 98, 0, 7, -126, 2, 23, 2, -90, 122, -29, 5, 0, 7, -93, -126, -62, 112, -82, 95, 118, -79, 0, 7, -53, -63, 108, 23, -101, -105, 10, -29, 0, 7, 58, -95, -8, 109, 16, -49, 115, -74, 0, 7, -53, -8, -93, 117, 38, -5, 72, 115, 0, 7, 1, 122, 6, -73, -121, -41, -120, -113, 0, 7, 36, -70, 31, 114, -125, -61, 85, -81, 0, 7, 4, -43, 102, -73, -100, -116, 56, -77, 0, 7, -48, -11, 51, -125, -77, -61, -65, -34, 0, 7, -118, -112, 66, 59, -87, 55, 11, 124, 0, 7, 87, 19, 0, -104, 76, -108, 18, -128, 0, 7, 14, 119, -50, -37, -96, 35, -68, 68, 0, 7, 2, -34, 14, 49, 115, 23, -90, -14, 0, 7, -99, -98, 60, 70, -75, -111, 34, -128, 0, 7, 1, 18, 93, 29, -37, 127, 38, 30, 0, 7, 17, 3, -78, 121, -4, -86, 23, 4, 0, 7, -94, 16, 7, 92, -125, -53, -122, 125, 0, 7, -102, 1, -78, -28, -113, -23, -20, 108, 0, 7, -57, -54, -6, 116, -80, 34, 63, 65, 0, }; }