1/*
2 * Copyright (C) 2011 Google Inc.
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
17package benchmarks.regression;
18
19public class IntegerBenchmark {
20    public int timeLongSignumBranch(int reps) {
21        int t = 0;
22        for (int i = 0; i < reps; ++i) {
23            t += signum1(-i);
24            t += signum1(0);
25            t += signum1(i);
26        }
27        return t;
28    }
29
30    public int timeLongSignumBranchFree(int reps) {
31        int t = 0;
32        for (int i = 0; i < reps; ++i) {
33            t += signum2(-i);
34            t += signum2(0);
35            t += signum2(i);
36        }
37        return t;
38    }
39
40    private static int signum1(long v) {
41        return v < 0 ? -1 : (v == 0 ? 0 : 1);
42    }
43
44    private static int signum2(long v) {
45        return ((int)(v >> 63)) | (int) (-v >>> 63); // Hacker's delight 2-7
46    }
47
48    public int timeLongBitCount_BitSet(int reps) {
49        int t = 0;
50        for (int i = 0; i < reps; ++i) {
51            t += pop((long) i);
52        }
53        return t;
54    }
55
56    private static int pop(long l) {
57        int count = popX(l & 0xffffffffL);
58        count += popX(l >>> 32);
59        return count;
60    }
61
62    private static int popX(long x) {
63        // BEGIN android-note
64        // delegate to Integer.bitCount(i); consider using native code
65        // END android-note
66        x = x - ((x >>> 1) & 0x55555555);
67        x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
68        x = (x + (x >>> 4)) & 0x0f0f0f0f;
69        x = x + (x >>> 8);
70        x = x + (x >>> 16);
71        return (int) x & 0x0000003f;
72    }
73
74    public int timeLongBitCount_2Int(int reps) {
75        int t = 0;
76        for (int i = 0; i < reps; ++i) {
77            t += pop2((long) i);
78        }
79        return t;
80    }
81
82    private static int pop2(long l) {
83        int count = Integer.bitCount((int) (l & 0xffffffffL));
84        count += Integer.bitCount((int) (l >>> 32));
85        return count;
86    }
87
88    public int timeLongBitCount_Long(int reps) {
89        int t = 0;
90        for (int i = 0; i < reps; ++i) {
91            t += Long.bitCount((long) i);
92        }
93        return t;
94    }
95
96    /**
97     * Table for Seal's algorithm for Number of Trailing Zeros. Hacker's Delight
98     * online, Figure 5-18 (http://www.hackersdelight.org/revisions.pdf)
99     * The entries whose value is -1 are never referenced.
100     */
101    private static final byte[] NTZ_TABLE = {
102        32,  0,  1, 12,  2,  6, -1, 13,   3, -1,  7, -1, -1, -1, -1, 14,
103        10,  4, -1, -1,  8, -1, -1, 25,  -1, -1, -1, -1, -1, 21, 27, 15,
104        31, 11,  5, -1, -1, -1, -1, -1,   9, -1, -1, 24, -1, -1, 20, 26,
105        30, -1, -1, -1, -1, 23, -1, 19,  29, -1, 22, 18, 28, 17, 16, -1
106    };
107
108    private static int numberOfTrailingZerosHD(int i) {
109        // Seal's algorithm - Hacker's Delight 5-18
110        i &= -i;
111        i = (i <<  4) + i;    // x *= 17
112        i = (i <<  6) + i;    // x *= 65
113        i = (i << 16) - i;    // x *= 65535
114        return NTZ_TABLE[i >>> 26];
115    }
116
117    private static int numberOfTrailingZerosOL(int i) {
118        return NTZ_TABLE[((i & -i) * 0x0450FBAF) >>> 26];
119    }
120
121    public int timeNumberOfTrailingZerosHD(int reps) {
122        int t = 0;
123        for (int i = 0; i < reps; ++i) {
124            t += numberOfTrailingZerosHD(i);
125        }
126        return t;
127    }
128
129    public int timeNumberOfTrailingZerosOL(int reps) {
130        int t = 0;
131        for (int i = 0; i < reps; ++i) {
132            t += numberOfTrailingZerosOL(i);
133        }
134        return t;
135    }
136
137    public int timeIntegerValueOf(int reps) throws Exception {
138        String[] intStrings = new String[]{"0", "1", "12", "123", "1234", "12345",
139                                           "123456", "1234567", "12345678"};
140        int t = 0;
141        for (int i = 0; i < reps; ++i) {
142            for (int j = 0; j < intStrings.length; ++j) {
143                t += Integer.valueOf(intStrings[j]);
144            }
145        }
146        return t;
147    }
148}
149