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 */ 20public class Main { 21 22 // TODO: lower precision still coming, b/64091002 23 24 // TODO: consider unsigned SAD too, b/64091002 25 26 private static char sadChar2Char(char[] s1, char[] s2) { 27 int min_length = Math.min(s1.length, s2.length); 28 char sad = 0; 29 for (int i = 0; i < min_length; i++) { 30 sad += Math.abs(s1[i] - s2[i]); 31 } 32 return sad; 33 } 34 35 private static char sadChar2CharAlt(char[] s1, char[] s2) { 36 int min_length = Math.min(s1.length, s2.length); 37 char sad = 0; 38 for (int i = 0; i < min_length; i++) { 39 char s = s1[i]; 40 char p = s2[i]; 41 sad += s >= p ? s - p : p - s; 42 } 43 return sad; 44 } 45 46 private static char sadChar2CharAlt2(char[] s1, char[] s2) { 47 int min_length = Math.min(s1.length, s2.length); 48 char sad = 0; 49 for (int i = 0; i < min_length; i++) { 50 char s = s1[i]; 51 char p = s2[i]; 52 int x = s - p; 53 if (x < 0) x = -x; 54 sad += x; 55 } 56 return sad; 57 } 58 59 /// CHECK-START: int Main.sadChar2Int(char[], char[]) loop_optimization (before) 60 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 61 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 62 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 63 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 64 /// CHECK-DAG: <<Get1:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 65 /// CHECK-DAG: <<Get2:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 66 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 67 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 68 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 69 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 70 // 71 /// CHECK-START: int Main.sadChar2Int(char[], char[]) loop_optimization (after) 72 /// CHECK-NOT: VecSADAccumulate 73 private static int sadChar2Int(char[] s1, char[] s2) { 74 int min_length = Math.min(s1.length, s2.length); 75 int sad = 0; 76 for (int i = 0; i < min_length; i++) { 77 sad += Math.abs(s1[i] - s2[i]); 78 } 79 return sad; 80 } 81 82 /// CHECK-START: int Main.sadChar2IntAlt(char[], char[]) loop_optimization (before) 83 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 84 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 85 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 86 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 87 /// CHECK-DAG: <<Get1:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 88 /// CHECK-DAG: <<Get2:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 89 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get2>>,<<Get1>>] loop:<<Loop>> outer_loop:none 90 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 91 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 92 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 93 // 94 /// CHECK-START: int Main.sadChar2IntAlt(char[], char[]) loop_optimization (after) 95 /// CHECK-NOT: VecSADAccumulate 96 private static int sadChar2IntAlt(char[] s1, char[] s2) { 97 int min_length = Math.min(s1.length, s2.length); 98 int sad = 0; 99 for (int i = 0; i < min_length; i++) { 100 char s = s1[i]; 101 char p = s2[i]; 102 sad += s >= p ? s - p : p - s; 103 } 104 return sad; 105 } 106 107 /// CHECK-START: int Main.sadChar2IntAlt2(char[], char[]) loop_optimization (before) 108 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 109 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 110 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 111 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 112 /// CHECK-DAG: <<Get1:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 113 /// CHECK-DAG: <<Get2:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 114 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 115 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 116 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 117 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 118 // 119 /// CHECK-START: int Main.sadChar2IntAlt2(char[], char[]) loop_optimization (after) 120 /// CHECK-NOT: VecSADAccumulate 121 private static int sadChar2IntAlt2(char[] s1, char[] s2) { 122 int min_length = Math.min(s1.length, s2.length); 123 int sad = 0; 124 for (int i = 0; i < min_length; i++) { 125 char s = s1[i]; 126 char p = s2[i]; 127 int x = s - p; 128 if (x < 0) x = -x; 129 sad += x; 130 } 131 return sad; 132 } 133 134 /// CHECK-START: long Main.sadChar2Long(char[], char[]) loop_optimization (before) 135 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 136 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 137 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 138 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 139 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 140 /// CHECK-DAG: <<Get1:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 141 /// CHECK-DAG: <<Get2:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 142 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 143 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 144 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 145 /// CHECK-DAG: <<Intrin:j\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsLong loop:<<Loop>> outer_loop:none 146 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 147 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 148 // 149 /// CHECK-START: long Main.sadChar2Long(char[], char[]) loop_optimization (after) 150 /// CHECK-NOT: VecSADAccumulate 151 private static long sadChar2Long(char[] s1, char[] s2) { 152 int min_length = Math.min(s1.length, s2.length); 153 long sad = 0; 154 for (int i = 0; i < min_length; i++) { 155 long x = s1[i]; 156 long y = s2[i]; 157 sad += Math.abs(x - y); 158 } 159 return sad; 160 } 161 162 /// CHECK-START: long Main.sadChar2LongAt1(char[], char[]) loop_optimization (before) 163 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 164 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 165 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 166 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 167 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 168 /// CHECK-DAG: <<Get1:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 169 /// CHECK-DAG: <<Get2:c\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 170 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 171 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 172 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 173 /// CHECK-DAG: <<Intrin:j\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsLong loop:<<Loop>> outer_loop:none 174 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 175 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 176 // 177 /// CHECK-START: long Main.sadChar2LongAt1(char[], char[]) loop_optimization (after) 178 /// CHECK-NOT: VecSADAccumulate 179 private static long sadChar2LongAt1(char[] s1, char[] s2) { 180 int min_length = Math.min(s1.length, s2.length); 181 long sad = 1; // starts at 1 182 for (int i = 0; i < min_length; i++) { 183 long x = s1[i]; 184 long y = s2[i]; 185 sad += Math.abs(x - y); 186 } 187 return sad; 188 } 189 190 public static void main(String[] args) { 191 // Cross-test the two most extreme values individually. 192 char[] s1 = { 0, 0x8000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 193 char[] s2 = { 0, 0x7fff, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 194 expectEquals(1, sadChar2Char(s1, s2)); 195 expectEquals(1, sadChar2Char(s2, s1)); 196 expectEquals(1, sadChar2CharAlt(s1, s2)); 197 expectEquals(1, sadChar2CharAlt(s2, s1)); 198 expectEquals(1, sadChar2CharAlt2(s1, s2)); 199 expectEquals(1, sadChar2CharAlt2(s2, s1)); 200 expectEquals(1, sadChar2Int(s1, s2)); 201 expectEquals(1, sadChar2Int(s2, s1)); 202 expectEquals(1, sadChar2IntAlt(s1, s2)); 203 expectEquals(1, sadChar2IntAlt(s2, s1)); 204 expectEquals(1, sadChar2IntAlt2(s1, s2)); 205 expectEquals(1, sadChar2IntAlt2(s2, s1)); 206 expectEquals(1L, sadChar2Long(s1, s2)); 207 expectEquals(1L, sadChar2Long(s2, s1)); 208 expectEquals(2L, sadChar2LongAt1(s1, s2)); 209 expectEquals(2L, sadChar2LongAt1(s2, s1)); 210 211 // Use cross-values to test all cases. 212 char[] interesting = { 213 (char) 0x0000, 214 (char) 0x0001, 215 (char) 0x0002, 216 (char) 0x1234, 217 (char) 0x8000, 218 (char) 0x8001, 219 (char) 0x7fff, 220 (char) 0xffff 221 }; 222 int n = interesting.length; 223 int m = n * n + 1; 224 s1 = new char[m]; 225 s2 = new char[m]; 226 int k = 0; 227 for (int i = 0; i < n; i++) { 228 for (int j = 0; j < n; j++) { 229 s1[k] = interesting[i]; 230 s2[k] = interesting[j]; 231 k++; 232 } 233 } 234 s1[k] = 10; 235 s2[k] = 2; 236 expectEquals(56196, sadChar2Char(s1, s2)); 237 expectEquals(56196, sadChar2CharAlt(s1, s2)); 238 expectEquals(56196, sadChar2CharAlt2(s1, s2)); 239 expectEquals(1497988, sadChar2Int(s1, s2)); 240 expectEquals(1497988, sadChar2IntAlt(s1, s2)); 241 expectEquals(1497988, sadChar2IntAlt2(s1, s2)); 242 expectEquals(1497988L, sadChar2Long(s1, s2)); 243 expectEquals(1497989L, sadChar2LongAt1(s1, s2)); 244 245 System.out.println("passed"); 246 } 247 248 private static void expectEquals(int expected, int result) { 249 if (expected != result) { 250 throw new Error("Expected: " + expected + ", found: " + result); 251 } 252 } 253 254 private static void expectEquals(long expected, long result) { 255 if (expected != result) { 256 throw new Error("Expected: " + expected + ", found: " + result); 257 } 258 } 259} 260