1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 /** 18 * Tests for SAD (sum of absolute differences). 19 */ 20 public class Main { 21 22 // TODO: lower precision still coming, b/64091002 23 24 private static byte sadByte2Byte(byte[] b1, byte[] b2) { 25 int min_length = Math.min(b1.length, b2.length); 26 byte sad = 0; 27 for (int i = 0; i < min_length; i++) { 28 sad += Math.abs(b1[i] - b2[i]); 29 } 30 return sad; 31 } 32 33 private static byte sadByte2ByteAlt(byte[] b1, byte[] b2) { 34 int min_length = Math.min(b1.length, b2.length); 35 byte sad = 0; 36 for (int i = 0; i < min_length; i++) { 37 byte s = b1[i]; 38 byte p = b2[i]; 39 sad += s >= p ? s - p : p - s; 40 } 41 return sad; 42 } 43 44 private static byte sadByte2ByteAlt2(byte[] b1, byte[] b2) { 45 int min_length = Math.min(b1.length, b2.length); 46 byte sad = 0; 47 for (int i = 0; i < min_length; i++) { 48 byte s = b1[i]; 49 byte p = b2[i]; 50 int x = s - p; 51 if (x < 0) x = -x; 52 sad += x; 53 } 54 return sad; 55 } 56 57 private static short sadByte2Short(byte[] b1, byte[] b2) { 58 int min_length = Math.min(b1.length, b2.length); 59 short sad = 0; 60 for (int i = 0; i < min_length; i++) { 61 sad += Math.abs(b1[i] - b2[i]); 62 } 63 return sad; 64 } 65 66 private static short sadByte2ShortAlt(byte[] b1, byte[] b2) { 67 int min_length = Math.min(b1.length, b2.length); 68 short sad = 0; 69 for (int i = 0; i < min_length; i++) { 70 byte s = b1[i]; 71 byte p = b2[i]; 72 sad += s >= p ? s - p : p - s; 73 } 74 return sad; 75 } 76 77 private static short sadByte2ShortAlt2(byte[] b1, byte[] b2) { 78 int min_length = Math.min(b1.length, b2.length); 79 short sad = 0; 80 for (int i = 0; i < min_length; i++) { 81 byte s = b1[i]; 82 byte p = b2[i]; 83 int x = s - p; 84 if (x < 0) x = -x; 85 sad += x; 86 } 87 return sad; 88 } 89 90 /// CHECK-START: int Main.sadByte2Int(byte[], byte[]) loop_optimization (before) 91 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 92 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 93 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 94 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 95 /// CHECK-DAG: <<Get1:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 96 /// CHECK-DAG: <<Get2:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 97 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 98 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 99 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 100 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 101 // 102 /// CHECK-START-{ARM64,MIPS64}: int Main.sadByte2Int(byte[], byte[]) loop_optimization (after) 103 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 104 /// CHECK-DAG: <<Cons16:i\d+>> IntConstant 16 loop:none 105 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<Cons0>>] loop:none 106 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 107 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 108 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 109 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 110 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 111 /// CHECK-DAG: Add [<<Phi1>>,<<Cons16>>] loop:<<Loop>> outer_loop:none 112 private static int sadByte2Int(byte[] b1, byte[] b2) { 113 int min_length = Math.min(b1.length, b2.length); 114 int sad = 0; 115 for (int i = 0; i < min_length; i++) { 116 sad += Math.abs(b1[i] - b2[i]); 117 } 118 return sad; 119 } 120 121 /// CHECK-START: int Main.sadByte2IntAlt(byte[], byte[]) loop_optimization (before) 122 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 123 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 124 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 125 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 126 /// CHECK-DAG: <<Get1:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 127 /// CHECK-DAG: <<Get2:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 128 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get2>>,<<Get1>>] loop:<<Loop>> outer_loop:none 129 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 130 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 131 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 132 // 133 /// CHECK-START-{ARM64,MIPS64}: int Main.sadByte2IntAlt(byte[], byte[]) loop_optimization (after) 134 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 135 /// CHECK-DAG: <<Cons16:i\d+>> IntConstant 16 loop:none 136 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<Cons0>>] loop:none 137 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 138 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 139 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 140 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 141 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load2>>,<<Load1>>] loop:<<Loop>> outer_loop:none 142 /// CHECK-DAG: Add [<<Phi1>>,<<Cons16>>] loop:<<Loop>> outer_loop:none 143 private static int sadByte2IntAlt(byte[] b1, byte[] b2) { 144 int min_length = Math.min(b1.length, b2.length); 145 int sad = 0; 146 for (int i = 0; i < min_length; i++) { 147 byte s = b1[i]; 148 byte p = b2[i]; 149 sad += s >= p ? s - p : p - s; 150 } 151 return sad; 152 } 153 154 /// CHECK-START: int Main.sadByte2IntAlt2(byte[], byte[]) loop_optimization (before) 155 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 156 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 157 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 158 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 159 /// CHECK-DAG: <<Get1:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 160 /// CHECK-DAG: <<Get2:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 161 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 162 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 163 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 164 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 165 // 166 /// CHECK-START-{ARM64,MIPS64}: int Main.sadByte2IntAlt2(byte[], byte[]) loop_optimization (after) 167 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 168 /// CHECK-DAG: <<Cons16:i\d+>> IntConstant 16 loop:none 169 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<Cons0>>] loop:none 170 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 171 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 172 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 173 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 174 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 175 /// CHECK-DAG: Add [<<Phi1>>,<<Cons16>>] loop:<<Loop>> outer_loop:none 176 private static int sadByte2IntAlt2(byte[] b1, byte[] b2) { 177 int min_length = Math.min(b1.length, b2.length); 178 int sad = 0; 179 for (int i = 0; i < min_length; i++) { 180 byte s = b1[i]; 181 byte p = b2[i]; 182 int x = s - p; 183 if (x < 0) x = -x; 184 sad += x; 185 } 186 return sad; 187 } 188 189 /// CHECK-START: long Main.sadByte2Long(byte[], byte[]) loop_optimization (before) 190 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 191 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 192 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 193 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 194 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 195 /// CHECK-DAG: <<Get1:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 196 /// CHECK-DAG: <<Get2:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 197 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 198 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 199 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 200 /// CHECK-DAG: <<Intrin:j\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsLong loop:<<Loop>> outer_loop:none 201 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 202 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 203 // 204 /// CHECK-START-{ARM64,MIPS64}: long Main.sadByte2Long(byte[], byte[]) loop_optimization (after) 205 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 206 /// CHECK-DAG: <<Cons16:i\d+>> IntConstant 16 loop:none 207 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 208 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 209 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 210 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 211 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 212 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 213 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 214 /// CHECK-DAG: Add [<<Phi1>>,<<Cons16>>] loop:<<Loop>> outer_loop:none 215 private static long sadByte2Long(byte[] b1, byte[] b2) { 216 int min_length = Math.min(b1.length, b2.length); 217 long sad = 0; 218 for (int i = 0; i < min_length; i++) { 219 long x = b1[i]; 220 long y = b2[i]; 221 sad += Math.abs(x - y); 222 } 223 return sad; 224 } 225 226 /// CHECK-START: long Main.sadByte2LongAt1(byte[], byte[]) loop_optimization (before) 227 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 228 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 229 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 230 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 231 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 232 /// CHECK-DAG: <<Get1:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 233 /// CHECK-DAG: <<Get2:b\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 234 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 235 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 236 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 237 /// CHECK-DAG: <<Intrin:j\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsLong loop:<<Loop>> outer_loop:none 238 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 239 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 240 // 241 /// CHECK-START-{ARM64,MIPS64}: long Main.sadByte2LongAt1(byte[], byte[]) loop_optimization (after) 242 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 243 /// CHECK-DAG: <<Cons16:i\d+>> IntConstant 16 loop:none 244 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 245 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 246 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 247 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 248 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 249 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 250 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 251 /// CHECK-DAG: Add [<<Phi1>>,<<Cons16>>] loop:<<Loop>> outer_loop:none 252 private static long sadByte2LongAt1(byte[] b1, byte[] b2) { 253 int min_length = Math.min(b1.length, b2.length); 254 long sad = 1; // starts at 1 255 for (int i = 0; i < min_length; i++) { 256 long x = b1[i]; 257 long y = b2[i]; 258 sad += Math.abs(x - y); 259 } 260 return sad; 261 } 262 263 public static void main(String[] args) { 264 // Cross-test the two most extreme values individually. 265 byte[] b1 = { 0, -128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 266 byte[] b2 = { 0, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 267 expectEquals(-1, sadByte2Byte(b1, b2)); 268 expectEquals(-1, sadByte2Byte(b2, b1)); 269 expectEquals(-1, sadByte2ByteAlt(b1, b2)); 270 expectEquals(-1, sadByte2ByteAlt(b2, b1)); 271 expectEquals(-1, sadByte2ByteAlt2(b1, b2)); 272 expectEquals(-1, sadByte2ByteAlt2(b2, b1)); 273 expectEquals(255, sadByte2Short(b1, b2)); 274 expectEquals(255, sadByte2Short(b2, b1)); 275 expectEquals(255, sadByte2ShortAlt(b1, b2)); 276 expectEquals(255, sadByte2ShortAlt(b2, b1)); 277 expectEquals(255, sadByte2ShortAlt2(b1, b2)); 278 expectEquals(255, sadByte2ShortAlt2(b2, b1)); 279 expectEquals(255, sadByte2Int(b1, b2)); 280 expectEquals(255, sadByte2Int(b2, b1)); 281 expectEquals(255, sadByte2IntAlt(b1, b2)); 282 expectEquals(255, sadByte2IntAlt(b2, b1)); 283 expectEquals(255, sadByte2IntAlt2(b1, b2)); 284 expectEquals(255, sadByte2IntAlt2(b2, b1)); 285 expectEquals(255, sadByte2Long(b1, b2)); 286 expectEquals(255L, sadByte2Long(b2, b1)); 287 expectEquals(256L, sadByte2LongAt1(b1, b2)); 288 expectEquals(256L, sadByte2LongAt1(b2, b1)); 289 290 // Use cross-values to test all cases. 291 // One for scalar cleanup. 292 int n = 256; 293 int m = n * n + 1; 294 int k = 0; 295 b1 = new byte[m]; 296 b2 = new byte[m]; 297 for (int i = 0; i < n; i++) { 298 for (int j = 0; j < n; j++) { 299 b1[k] = (byte) i; 300 b2[k] = (byte) j; 301 k++; 302 } 303 } 304 b1[k] = 10; 305 b2[k] = 2; 306 expectEquals(8, sadByte2Byte(b1, b2)); 307 expectEquals(8, sadByte2ByteAlt(b1, b2)); 308 expectEquals(8, sadByte2ByteAlt2(b1, b2)); 309 expectEquals(21768, sadByte2Short(b1, b2)); 310 expectEquals(21768, sadByte2ShortAlt(b1, b2)); 311 expectEquals(21768, sadByte2ShortAlt2(b1, b2)); 312 expectEquals(5592328, sadByte2Int(b1, b2)); 313 expectEquals(5592328, sadByte2IntAlt(b1, b2)); 314 expectEquals(5592328, sadByte2IntAlt2(b1, b2)); 315 expectEquals(5592328L, sadByte2Long(b1, b2)); 316 expectEquals(5592329L, sadByte2LongAt1(b1, b2)); 317 318 System.out.println("passed"); 319 } 320 321 private static void expectEquals(int expected, int result) { 322 if (expected != result) { 323 throw new Error("Expected: " + expected + ", found: " + result); 324 } 325 } 326 327 private static void expectEquals(long expected, long result) { 328 if (expected != result) { 329 throw new Error("Expected: " + expected + ", found: " + result); 330 } 331 } 332 } 333