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 SimdSadChar {
21 
22   // TODO: lower precision still coming, b/64091002
23 
24   // TODO: consider unsigned SAD too, b/64091002
25 
sadChar2Char(char[] s1, char[] s2)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 
sadChar2CharAlt(char[] s1, char[] s2)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 
sadChar2CharAlt2(char[] s1, char[] s2)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 SimdSadChar.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: <<Phi2:i\d+>>   Phi [<<Cons0>>,{{i\d+}}]       loop:<<Loop:B\d+>> outer_loop:none
63   /// CHECK-DAG: <<Phi1: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+>> Abs [<<Sub>>]                  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 SimdSadChar.sadChar2Int(char[], char[]) loop_optimization (after)
72   /// CHECK-NOT: VecSADAccumulate
sadChar2Int(char[] s1, char[] s2)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 SimdSadChar.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: <<Phi2:i\d+>>   Phi [<<Cons0>>,{{i\d+}}]       loop:<<Loop:B\d+>> outer_loop:none
86   /// CHECK-DAG: <<Phi1: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+>> Abs [<<Sub>>]                  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 SimdSadChar.sadChar2IntAlt(char[], char[]) loop_optimization (after)
95   /// CHECK-NOT: VecSADAccumulate
sadChar2IntAlt(char[] s1, char[] s2)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 SimdSadChar.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: <<Phi2:i\d+>>   Phi [<<Cons0>>,{{i\d+}}]       loop:<<Loop:B\d+>> outer_loop:none
111   /// CHECK-DAG: <<Phi1: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+>> Abs [<<Sub>>]                  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 SimdSadChar.sadChar2IntAlt2(char[], char[]) loop_optimization (after)
120   /// CHECK-NOT: VecSADAccumulate
sadChar2IntAlt2(char[] s1, char[] s2)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 SimdSadChar.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+>> Abs [<<Sub>>]                  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 SimdSadChar.sadChar2Long(char[], char[]) loop_optimization (after)
150   /// CHECK-NOT: VecSADAccumulate
sadChar2Long(char[] s1, char[] s2)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 SimdSadChar.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+>> Abs [<<Sub>>]                  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 SimdSadChar.sadChar2LongAt1(char[], char[]) loop_optimization (after)
178   /// CHECK-NOT: VecSADAccumulate
sadChar2LongAt1(char[] s1, char[] s2)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 
main()190   public static void main() {
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("SimdSadChar passed");
246   }
247 
expectEquals(int expected, int result)248   private static void expectEquals(int expected, int result) {
249     if (expected != result) {
250       throw new Error("Expected: " + expected + ", found: " + result);
251     }
252   }
253 
expectEquals(long expected, long result)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