Home | History | Annotate | Download | only in arch 
      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 
     21 class 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 
     33 class 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.
     38 int32_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 
     47 static constexpr size_t kMemCmp16Rounds = 100000;
     48 
     49 static 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 
    156 TEST_F(MemCmp16Test, RandomSeparateShort) {
    157   CheckSeparate(5U, 1U);
    158 }
    159 
    160 TEST_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