grub-core/tests/shift_test.c

   1 /*
   2  *  GRUB  --  GRand Unified Bootloader
   3  *  Copyright (C) 2015 Free Software Foundation, Inc.
   4  *
   5  *  GRUB is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  GRUB is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <grub/test.h>
  20 #include <grub/dl.h>
  21 #include <grub/misc.h>
  22
  23 GRUB_MOD_LICENSE ("GPLv3+");
  24
  25 static grub_uint64_t vectors[] = {
  26   0xffffffffffffffffULL, 1, 2, 0, 0x0102030405060708ULL
  27 };
  28
  29 /* We're testing shifts, don't replace access to this with a shift.  */
  30 static const grub_uint8_t bitmask[] =
  31   { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
  32
  33 typedef union {
  34   grub_uint64_t v64;
  35   grub_uint8_t v8[8];
  36 } grub_raw_u64_t;
  37
  38 static int
  39 get_bit64 (grub_uint64_t v, int b)
  40 {
  41   grub_raw_u64_t vr = { .v64 = v };
  42   grub_uint8_t *p = vr.v8;
  43   if (b >= 64)
  44     return 0;
  45 #ifdef GRUB_CPU_WORDS_BIGENDIAN
  46   p += 7 - b / 8;
  47 #else
  48   p += b / 8;
  49 #endif
  50   return !!(*p & bitmask[b % 8]);
  51 }
  52
  53 static grub_uint64_t
  54 set_bit64 (grub_uint64_t v, int b)
  55 {
  56   grub_raw_u64_t vr = { .v64 = v };
  57   grub_uint8_t *p = vr.v8;
  58   if (b >= 64)
  59     return v;
  60 #ifdef GRUB_CPU_WORDS_BIGENDIAN
  61   p += 7 - b / 8;
  62 #else
  63   p += b / 8;
  64 #endif
  65   *p |= bitmask[b % 8];
  66   return vr.v64;
  67 }
  68
  69 static grub_uint64_t
  70 left_shift64 (grub_uint64_t v, int s)
  71 {
  72   grub_uint64_t r = 0;
  73   int i;
  74   for (i = 0; i + s < 64; i++)
  75     if (get_bit64 (v, i))
  76       r = set_bit64 (r, i + s);
  77   return r;
  78 }
  79
  80 static grub_uint64_t
  81 right_shift64 (grub_uint64_t v, int s)
  82 {
  83   grub_uint64_t r = 0;
  84   int i;
  85   for (i = s; i < 64; i++)
  86     if (get_bit64 (v, i))
  87       r = set_bit64 (r, i - s);
  88   return r;
  89 }
  90
  91 static grub_uint64_t
  92 arithmetic_right_shift64 (grub_uint64_t v, int s)
  93 {
  94   grub_uint64_t r = 0;
  95   int i;
  96   for (i = s; i < 64; i++)
  97     if (get_bit64 (v, i))
  98       r = set_bit64 (r, i - s);
  99   if (get_bit64 (v, 63))
 100     for (i -= s; i < 64; i++)
 101         r = set_bit64 (r, i);
 102
 103   return r;
 104 }
 105
 106 static void
 107 test64 (grub_uint64_t v)
 108 {
 109   int i;
 110   for (i = 0; i < 64; i++)
 111     {
 112       grub_test_assert ((v << i) == left_shift64 (v, i),
 113                         "lshift wrong: 0x%llx << %d: 0x%llx, 0x%llx",
 114                         (long long) v, i,
 115                         (long long) (v << i), (long long) left_shift64 (v, i));
 116       grub_test_assert ((v >> i) == right_shift64 (v, i),
 117                         "rshift wrong: 0x%llx >> %d: 0x%llx, 0x%llx",
 118                         (long long) v, i,
 119                         (long long) (v >> i), (long long) right_shift64 (v, i));
 120       grub_test_assert ((((grub_int64_t) v) >> i) == (grub_int64_t) arithmetic_right_shift64 (v, i),
 121                         "arithmetic rshift wrong: ((grub_int64_t) 0x%llx) >> %d: 0x%llx, 0x%llx",
 122                         (long long) v, i,
 123                         (long long) (((grub_int64_t) v) >> i), (long long) arithmetic_right_shift64 (v, i));
 124     }
 125 }
 126
 127 static void
 128 test_all(grub_uint64_t a)
 129 {
 130   test64 (a);
 131 }
 132
 133 static void
 134 shift_test (void)
 135 {
 136   grub_uint64_t a = 404, b = 7;
 137   grub_size_t i;
 138
 139   for (i = 0; i < ARRAY_SIZE (vectors); i++)
 140     {
 141       test_all (vectors[i]);
 142     }
 143   for (i = 0; i < 4000; i++)
 144     {
 145       a = 17 * a + 13 * b;
 146       b = 23 * a + 29 * b;
 147       if (b == 0)
 148         b = 1;
 149       if (a == 0)
 150         a = 1;
 151       test_all (a);
 152       test_all (b);
 153     }
 154 }
 155
 156 /* Register example_test method as a functional test.  */
 157 GRUB_FUNCTIONAL_TEST (shift_test, shift_test);