1/*
2 * Copyright (C) 2014 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#include "memcmp16.h"
18
19#include "gtest/gtest.h"
20
21class RandGen {
22 public:
23  explicit RandGen(uint32_t seed) : val_(seed) {}
24
25  uint32_t next() {
26    val_ = val_ * 48271 % 2147483647 + 13;
27    return val_;
28  }
29
30  uint32_t val_;
31};
32
33class MemCmp16Test : public testing::Test {
34};
35
36// A simple implementation to compare against.
37// Note: this version is equivalent to the generic one used when no optimized version is available.
38int32_t memcmp16_compare(const uint16_t* s0, const uint16_t* s1, size_t count) {
39  for (size_t i = 0; i < count; i++) {
40    if (s0[i] != s1[i]) {
41      return static_cast<int32_t>(s0[i]) - static_cast<int32_t>(s1[i]);
42    }
43  }
44  return 0;
45}
46
47static constexpr size_t kMemCmp16Rounds = 100000;
48
49static void CheckSeparate(size_t max_length, size_t min_length) {
50  RandGen r(0x1234);
51  size_t range_of_tests = 7;  // All four (weighted) tests active in the beginning.
52
53  for (size_t round = 0; round < kMemCmp16Rounds; ++round) {
54    size_t type = r.next() % range_of_tests;
55    size_t count1, count2;
56    uint16_t *s1, *s2;  // Use raw pointers to simplify using clobbered addresses
57
58    switch (type) {
59      case 0:  // random, non-zero lengths of both strings
60      case 1:
61      case 2:
62      case 3:
63        count1 = (r.next() % max_length) + min_length;
64        count2 = (r.next() % max_length) + min_length;
65        break;
66
67      case 4:  // random non-zero length of first, second is zero
68        count1 = (r.next() % max_length) + min_length;
69        count2 = 0U;
70        break;
71
72      case 5:  // random non-zero length of second, first is zero
73        count1 = 0U;
74        count2 = (r.next() % max_length) + min_length;
75        break;
76
77      case 6:  // both zero-length
78        count1 = 0U;
79        count2 = 0U;
80        range_of_tests = 6;  // Don't do zero-zero again.
81        break;
82
83      default:
84        ASSERT_TRUE(false) << "Should not get here.";
85        continue;
86    }
87
88    if (count1 > 0U) {
89      s1 = new uint16_t[count1];
90    } else {
91      // Leave a random pointer, should not be touched.
92      s1 = reinterpret_cast<uint16_t*>(0xebad1001);
93    }
94
95    if (count2 > 0U) {
96      s2 = new uint16_t[count2];
97    } else {
98      // Leave a random pointer, should not be touched.
99      s2 = reinterpret_cast<uint16_t*>(0xebad2002);
100    }
101
102    size_t min = count1 < count2 ? count1 : count2;
103    bool fill_same = r.next() % 2 == 1;
104
105    if (fill_same) {
106      for (size_t i = 0; i < min; ++i) {
107        s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
108        s2[i] = s1[i];
109      }
110      for (size_t i = min; i < count1; ++i) {
111        s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
112      }
113      for (size_t i = min; i < count2; ++i) {
114        s2[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
115      }
116    } else {
117      for (size_t i = 0; i < count1; ++i) {
118        s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
119      }
120      for (size_t i = 0; i < count2; ++i) {
121        s2[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
122      }
123    }
124
125    uint16_t* s1_pot_unaligned = s1;
126    uint16_t* s2_pot_unaligned = s2;
127    size_t c1_mod = count1;
128    size_t c2_mod = count2;
129
130    if (!fill_same) {  // Don't waste a good "long" test.
131      if (count1 > 1 && r.next() % 10 == 0) {
132        c1_mod--;
133        s1_pot_unaligned++;
134      }
135      if (count2 > 1 && r.next() % 10 == 0) {
136        c2_mod--;
137        s2_pot_unaligned++;
138      }
139    }
140    size_t mod_min = c1_mod < c2_mod ? c1_mod : c2_mod;
141
142    int32_t expected = memcmp16_compare(s1_pot_unaligned, s2_pot_unaligned, mod_min);
143    int32_t computed = art::testing::MemCmp16Testing(s1_pot_unaligned, s2_pot_unaligned, mod_min);
144
145    ASSERT_EQ(expected, computed) << "Run " << round << ", c1=" << count1 << " c2=" << count2;
146
147    if (count1 > 0U) {
148      delete[] s1;
149    }
150    if (count2 > 0U) {
151      delete[] s2;
152    }
153  }
154}
155
156TEST_F(MemCmp16Test, RandomSeparateShort) {
157  CheckSeparate(5U, 1U);
158}
159
160TEST_F(MemCmp16Test, RandomSeparateLong) {
161  CheckSeparate(64U, 32U);
162}
163
164// TODO: What's a good test for overlapping memory. Is it important?
165// TEST_F(MemCmp16Test, RandomOverlay) {
166//
167// }
168